1305_광고

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

1305번: 광고

 

 

역시 KMP알고리즘을 활용해 푸는 문제이다. 특히 KMP Table을 이용해서 풀 수있다.

 

예를들어서 

 

7

aabaaba라는 문자열이 있다고 생각하면 KMP Table을 구하면

 

[0, 1, 0, 1, 2, 3, 4]

가 나온다 즉, 광고판의 끝부분에서 보았을때 시작부터 4개의 지점이랑 겹친다는 의미이다.

 

그렇기 때문에 광고판의 개수에서 겹치는 개수를뺀

 

l - KMP_Table[-1]을 구하면 답을 구할 수 있다.

 

l = int(input())
str = input()
ls = len(str)
k = [0] *ls
j=0
for i in range(1,ls):
    while j>0 and str[i]!=str[j]:
        j= k[j-1]
    if str[i] == str[j]:
        j+=1
        k[i]=j
print(l-k[-1])