图论也挺难的，所以我选择复习一下字符串那些算法。
字符串算法第一个很重要的就是匹配了，也就是 \(KMP\) 算法，这里的话主要就是计算模式串的
\(Next\) 数组。那一位的 \(Next\)
数组的值相当于这一位之前的字符串的最大相同前后缀长度。
比如 \(baabaa\) 那么它的 \(Next\) 数组分别是 \(-1\ 0\ 0\ 0\ 1\ 2\) 。
为什么最开始的那个是 \(-1\)
呢，因为说了，当前的next所看的字符串是不包括当前字符的，所以第一个的next值所看的字符串其实是一个空串。并且我们可以想象一下，如果第一位它就不匹配，我要跳到哪？答案是模式串指针不跳，匹配串指针要跳。但是一般情况下失配是完全相反的，只有匹配的情况下j会往后跳，所以我们会把第一位失配和匹配的情况归为一类，或者是说特判一下第一位失配的情况，就让它跳到-1，如果跳到-1那么
\(i++,j++\) 就好了。
那么接下来我们做一道模板匹配题。
练习
为了防止被说水博客，这里就放三题好了。
标板 \(KMP\)，只不过就是说，最后要那你输出一下模式串从开头到
\(i\) 子串串的最长公共前后缀，这个跟
\(Next\) 的数组还是有点区别的啊。\(Next\)
的数组对应那一位是不包括这个字符的，所以这个输出的话从 \(1\) 到 \(n\) 输出就好了。
标程
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
31
32
33
34
35
36
37
38
39
40
41
| #include<bits/stdc++.h>
#define maxn 1000006
using namespace std;
char s[maxn];
char mod_str[maxn];
int kmp[maxn];
int main(){
scanf("%s%s",s,mod_str);
int len1=strlen(s),len2=strlen(mod_str);
for(int i=1;i<len1;i++){
int t=kmp[i];
while(mod_str[t]!=mod_str[i]&&t){
t=kmp[t];
}
if(mod_str[t]==mod_str[i]){
kmp[i+1]=t+1;
}
else{
kmp[i+1]=0;
}
}
kmp[0]=-1;
int j=0;
for(int i=0;i<len1;){
if(j==-1||s[i]==mod_str[j]){
i++;
j++;
}
else{
j=kmp[j];
}
if(j==len2){
printf("%d\n",i-j+1);
j=kmp[j];
}
}
for(int i=1;i<=len2;i++){
printf("%d ",kmp[i]);
}
return 0;
}
|
就是看看一个字符串它是哪个子串循环构成的。
比如
他就能看成是 \(aab\)
循环组成的一个字符串，但是。我们分析一下这样的字符串它的next数组看看
这里为什么多出一个3，因为匹配完成之后还得跳失配指针。这里可能不明显，但是你多写几个就会发现。
1
2
| aabaabaabaabaabaabaabaabaabaab
-1 0 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13……
|
结果已经显而易见了，我只要取得最后的next值，然后拿n减去它就可以算出循环大小了。
标程
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
| #include<bits/stdc++.h>
#define maxn 1000005
using namespace std;
char ss[maxn];
int kmp[maxn];
int main()
{
int n;
cin>>n;
scanf("%s",ss);
for(int i=1;i<n;i++){
int p=kmp[i];
while(ss[i]!=ss[p]&&p){
p=kmp[p];
}
if(ss[i]==ss[p]){
kmp[i+1]=p+1;
}
else{
kmp[i+1]=0;
}
}
printf("%d\n",n-kmp[n]);
}
|
就是算出所有前缀的最长可表示周期，并且这个周期长度应该小于这个前缀。
这个怎么说呢，就是假如 \(aaaaa\)
它会由哪个周期构成呢？结果有很多
以上都可以成为它的周期。
因为我们要找最长的所以说呢就选 \(aaaa\) 。
但是有一种情况是例外的，就是 \(aabaa\) 这个就有点不一样了，它看上去好像是
\(aab\) 最大周期，但是它最大周期可以到
\(aaba\)
，所以呢我们特判一下最后一个字符和第一个一不一样，一样就直接 \(n-1\) 就-好了。
然后就是遍历整个 \(next\)
数组。不过为了保证最长，我们还需要跳 \(fail\)，跳到不为0的时候即是最大周期，防止重复跳可以加一个优化，跳了之后直接把next值改掉，改成指向最终位置。
标程
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| #include<bits/stdc++.h>
#define int long long
#define maxn 1000005
using namespace std;
char s[maxn];
int kmp[maxn];
signed main(){
int n;
long long ans=0;
cin>>n;
scanf("%s",s);
for(int i=1;i<n;i++){
int p=kmp[i];
while(s[p]!=s[i]&&p){
p=kmp[p];
}
if(s[p]==s[i]){
kmp[i+1]=p+1;
}
else{
kmp[i+1]=0;
}
}
for(int i=0;i<n;i++){
if(kmp[i+1]){
if(s[i]==s[0]){
ans+=i;
}
else{
int x=kmp[i+1];
int q=i+1;
while(kmp[x]!=0){
x=kmp[x];
}
kmp[q]=x;
ans+=i-x+1;
}
}
}
printf("%lld\n",ans);
return 0;
}
|
