1786_찾기

https://www.acmicpc.net/problem/1786

1786번: 찾기

 

 

KMP알고리즘을 사용해서 풀면된다. 백준 문제 글에 설명이 자세히 되어있으니 알고리즘 자체는 설명을 읽으면 될 것 같다.

 

 

최대의 k를 미리 계산해 놓으면 편리할 것이다

 

라는 구절이 있는데 이를 먼저 구해두면 된다.

 

p를 처음부터 순환하면서 k를 저장해둘 공간을 넣어두면 된다. 해당 부분은 코드로 보는것이 좀 더 편할 것 같다.

 

t = input()
p = input()

k=[0 for _ in range(len(p))]
j=0
for i in range(1,len(p)):
    while j>0 and p[i]!=p[j]: # j랑 일치하지 않을때
        j = k[j-1] #가장 최근에 맞았던 부분으로 이동
    if p[i] == p[j]: #일치하면
        j+=1 #j값에 1 더해줌
        k[i]=j #k값 업데이트

result=[]
j=0
for i in range(len(t)):
    while j>0 and t[i]!=p[j]:
        j = k[j-1]
    if t[i]==p[j]:
        if j == len(p)-1:
            result.append(i-len(p)+2)
            j=k[j]
        else:
            j+=1

print(len(result))
print(*result)

k를 업데이트 하는 과정이 이해되어야 한다. 

 

만약 j랑 일치하지 않았을때 가장 최근에 맞았던 부분이 없다면 0으로 돌아갈 것이고, 맞는 부분이 있다면 해당하는 j값이 누적되서 기록될 것이다.

 

k를 업데이트 하는 과정이 이해되었다면 그 다음은 쉽다. t에 똑같이 적용하되, t랑 p랑 일치하는 부분이 있을때 만약 p랑 똑같다면 결과에 저장해두고, 그이후부터 다시 검사할 수 있게 j를 k[j]로 돌려주고 계속 검사를 진행하면 된다.