图论也挺难的,所以我选择复习一下字符串那些算法。

字符串算法第一个很重要的就是匹配了,也就是 $KMP$ 算法,这里的话主要就是计算模式串的 $Next$ 数组。那一位的 $Next$ 数组的值相当于这一位之前的字符串的最大相同前后缀长度。

比如 $baabaa$ 那么它的 $Next$ 数组分别是 $-1\ 0\ 0\ 0\ 1\ 2$ 。

为什么最开始的那个是 $-1$ 呢,因为说了,当前的next所看的字符串是不包括当前字符的,所以第一个的next值所看的字符串其实是一个空串。并且我们可以想象一下,如果第一位它就不匹配,我要跳到哪?答案是模式串指针不跳,匹配串指针要跳。但是一般情况下失配是完全相反的,只有匹配的情况下j会往后跳,所以我们会把第一位失配和匹配的情况归为一类,或者是说特判一下第一位失配的情况,就让它跳到-1,如果跳到-1那么 $i++,j++$ 就好了。

那么接下来我们做一道模板匹配题。

练习

为了防止被说水博客,这里就放三题好了。

洛谷P3375

标板 $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];//next数组
int main(){
scanf("%s%s",s,mod_str);
int len1=strlen(s),len2=strlen(mod_str);
for(int i=1;i<len1;i++){//计算模式串的next数组
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]);//输出next数组
}
return 0;
}

洛谷P4391

就是看看一个字符串它是哪个子串循环构成的。

比如

1
aabaab

他就能看成是 $aab$ 循环组成的一个字符串,但是。我们分析一下这样的字符串它的next数组看看

1
-1 0 0 0 1 2 3

这里为什么多出一个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()
{
//freopen("P4391_3.in","r",stdin);
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;
}
}
// for(int i=0;i<=n;i++){
// printf("%d ",kmp[i]);
// }
printf("%d\n",n-kmp[n]);
}

洛谷P3435

就是算出所有前缀的最长可表示周期,并且这个周期长度应该小于这个前缀。

这个怎么说呢,就是假如 $aaaaa$ 它会由哪个周期构成呢?结果有很多

1
2
3
4
a
aa
aaa
aaaa

以上都可以成为它的周期。

因为我们要找最长的所以说呢就选 $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(){
//freopen("1.in","r",stdin);
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;
//printf("%d's ans=%d\n",i,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("%d's ans=%d\n",i,i-x+1);
}
}
}

printf("%lld\n",ans);
return 0;
}