bzoj 1355: [Baltic2009]Radio Transmission

 1 #include<bits/stdc++.h>
 2 #define N 1000005
 3 #define LL long long
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 inline int ra()
 7 {
 8     int x=0,f=1; char ch=getchar();
 9     while (ch<‘0‘ || ch>‘9‘) {if (ch==‘-‘) f=-1; ch=getchar();}
10     while (ch>=‘0‘ && ch<=‘9‘) {x=x*10+ch-‘0‘; ch=getchar();}
11     return x*f;
12 }
13 char ch[N];
14 int fail[N];
15 int main()
16 {
17     int L=ra(); scanf("%s",ch+1);
18     int fix=0;
19     for (int i=2; i<=L; i++)
20     {
21         while (ch[fix+1]!=ch[i] && fix) fix=fail[fix];
22         if (ch[fix+1]==ch[i]) fix++;
23         fail[i]=fix;
24     }
25     printf("%d",L-fail[L]);
26     return 0;
27 }