3356번: Radio Transmission

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


$O(l)$

s에 관한 failure function을 f(x)라고 하면
답은 l-f(l)

#include<cstdio>
const int MXN = 1e6;
int l, a[MXN + 1] = { -1 };
char s[MXN + 1];
int main() {
    scanf("%d%s", &l, s);
    for (int i = 0, j = -1; i < l;) {
        if (j == -1 || s[i] == s[j]) a[++i] = ++j;
        else j = a[j];
    }
    printf("%d", l - a[l]);
    return 0;
}