백준 1305 : 광고

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

1305번: 광고

 

해결 방법 : Failure Function

• KMP 알고리즘에 대해 모르는 상태로 어떻게든 풀어보려다가 3시간 동안 시간초과를 해결하지 못했다...
• KMP 알고리즘에 사용되는 failure function을 적용하면 간단하게 풀리긴 하지만, 이해는 간단하지 않음..
• failure function은 문자열 안에서, 접두사와 접미사가 동일한 최대 길이를 찾는다. (참고 사이트)
  • AABAAABAA 를 예로 들면, failure function으로 [0,1,0,1,2,2,3,4,5]라는 table을 얻을 수 있다.
  • 여기서 마지막 값 5의 의미는 5번 연속으로 문자열의 접두사와 동일한 문자가 나타나고 있다는 뜻이다.
  • 즉, 처음부터 마지막 문자의 5번 이전까지의 부분 문자열이 중복되고 있는, 그리고 최소일 것으로 기대할 수 있는 문자열이 된다.

 

import sys
input = sys.stdin.readline

def solution(L, ad):
    failure = [0] * (L)
    l, r = 0, 1 # left, right
    while r < L: # failure function
        if ad[l] == ad[r]: # 문자가 같으면 l, r 모두 증가시켜 다음 문자 비교
            failure[r] = l + 1
            l += 1
            r += 1
        else:
            if l == 0: # l이 첫번째 문자이며, 문자가 다르기 때문에 r만 증가
                r += 1
            else: # l의 이전값의 failure function값을 l로 하여 다시 비교
                l = failure[l - 1]

    return L - failure[L-1]

if __name__ == '__main__':
    L = int(input())
    ad = input().strip()
    result = solution(L, ad)
    print(result)