Steven_MengのBlog

考虑到一个合法的$s$,长度为$n$,那么题目给的字符串(设为$a$,长度为$m$)肯定可以这么表示:

$s[1 \to n] + s[1 \to n] + s[1 \to n] … +s[1 \to n]+s[1 \to i]$

$1 \le i \le n$

考虑这个字符串的$next[n]$。

可以知道$s[1 \to next[n]]$的后$i$位肯定是$s[1 \to i]$,否则这个肯定不能匹配。

考虑离后$i$位最近的$s[1 \to i]$,发现出现在这里的前$i$位:

再演算一遍,发现前面的部分也可以匹配上。

于是$n - next[n]$是最小的解($next[n]$取所有合法的border的最大值)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define MAXN 1000005
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while (ch<'0'||ch>'9'){
if (ch=='-') f=-1;
ch=getchar();
}
while (ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^'0');
ch=getchar();
}
return x*f;
}
char s[MAXN];
int nex[MAXN];
int main(){
int n=read();
scanf("%s",s+1);
int j=0;
memset(nex,0,sizeof(nex));
for (register int i=2;i<=n;++i){
while (j>0&&s[j+1]!=s[i]) j=nex[j];
if (s[j+1]==s[i]) j++;
nex[i]=j;
}
printf("%d\n",n-nex[n]);
}

 评论