[Python]문자열 알고리즘1 백준 1305

   문제

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

광고판을 꽉채운 문자열이 주어진다.

우리는 이중에서 가장 짧은 광고를 찾는 문제라고 볼 수 있겠다.

문제를 해석하는 부분이 조금 난해하다. 광고 비용을 줄이기위해서 최대한 작은 광고판에

 만들기위해 필요한 광고판의 길이를 구하는 문제로 내었다면 좀더 이해가 쉬웠을거같다.

어쨋든 우리는 가장 짧은 광고를 찾으면 되고 실패함수를 통해 테이블의 끝값을 이용하여

 찾을수있다.

aabaaa 라면 부분일치 테이블은 

010122 이다.

마지막 문자열의 처음문자열로부터 2번재 까지 일치하므로 가장 짧은 광고는  aaba가 

되는것이다.

L=int(input())#광고판길이
s=input()#광고판의 문자열
s_len=len(s)
 
 
#실패함수
p_table=[0 for _ in range(s_len)]
j=0
for i in range(1,s_len):
    while j>0 and s[i]!=s[j]:
        j=p_table[j-1]
    if s[i]==s[j]:
        j+=1
        p_table[i]=j
 
p_len=s_len-p_table[s_len-1]#가장짧은 광고길이
print(p_len)