1305 광고

처음엔 좀 이해하기 어려웠다.

KMP를 이해하고 나면 그래도 좀 편하다

KMP의 P배열의 특성을 생각하면 prefix와 suffix가 같을 때 해당부분은 반복된 것이고 나머지가 전광판 길이상 나오지 않은 부분이라고 추측할 수 있다.

#include <stdio.h>
#include <iostream>
#define mv 1000002
 
char p[mv];
int f[mv], m;
 
int main() {
    scanf("%d\n", &m);
    fgets(p, mv, stdin);
    for (int i = 1, j = 0; i < m; i++) {
        while (j && p[i] != p[j]) j = f[j - 1];
        if (p[i] == p[j]) f[i] = ++j;
    }
    printf("%d\n", m - f[m - 1]);
    return 0;
}