백준[1305] 광고

문제 설명

풀이

kmp의 실패 함수를 이용하여 풀이할 수 있다.

전체 문자열 길이를 L, 실패함수 배열을 pi (pi는 0 인덱스부터 시작)라 하면 L - pi[L-1]로 문제의 정답을 구할 수 있다.

abcdab라는 문자열이 있을 때 pi[L-1]은 2이고 이 수는 반복되는 패턴 문자열인 abcd가 끝나고, 패턴 문자열 앞부분 ab 2 글자가 패턴 문자열에 붙은 거라고 볼 수 있다.

코드

#include <cstdio>

char s[1000006];
int pi[1000006], L;

int main() {
    scanf("%d %s", &L, s);
    int j = 0;
    for (int i = 1; i < L; i++) {
        while (j > 0 && s[i] != s[j]) j = pi[j - 1];
        if (s[i] == s[j]) pi[i] = ++j;
    }
    printf("%d", L - pi[L - 1]);
}