目录
  1. HDU-3746
  2. HDU-1385
  3. HUST-1010
  4. HDU-3377
KMP+循环节问题

HDU-3746

现在给你一个字符串,请问在该字符串末尾最少添加多少个字符,可以让这个字符串获得重复循环序列。

输入:第一行是一个整数 $T ( 0<T<=100 )$ 代表测试数据的组数。之后$T$行每行一个字符串,由小写字母组成,字符串的长度 $3<=L<=100000$。

输出:每组数据输出一行结果。

样例:

1
2
3
4
3
ppp
pip
machinelearning

1
2
3
0
1
15

思路:

循环节是指一段数据中重复的最小环。KMP不止要学会套模板匹配字符串,还要学到KMP算法的精髓——Next数组
(未经优化的)$Next[i]$指的 $S[0:i-1]$的最大共同前后缀长度(例如abcabcabc的共同前后缀为abcabc, abcabc为abc, abcabcabcabc为abc*3)
故一段字符串的循环节就是: $N - Next[N]$
将其记为len。若该字符串是循环字符串,则 $N\%len==0$, 而循环节的个数为:$N/len$
若不是,则 $Next[N] == 0$(abcd)或者$N\%len != 0$

题解

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
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;

int n;
char s[maxn];
int Next[maxm];

int getnext()
{
Next[0] = -1;
int i = 0, j = -1;
while(i<n)
{
while(j!=-1 && s[i]!=s[j]) j = Next[j];
Next[++i] = ++j;
}
int len = - Next[n] + n;
if(Next[n]==0) return len; //没有循环部分,只能自身成为循环节
else if(Next[n]%len==0) return 0; //已经是循环字符串
else return len - Next[n] % len; //需要补齐
}


int main()
{
int T;
cin >> T;
getchar();
while(T--)
{
scanf("%s", s);
n = strlen(s);
cout << getnext() << endl;
}
return 0;
}


HDU-1385

给出一个字符串s(1为起始),问在[1, i]区间是否有完整的循环节,若有,输出i并输出循环次数

1
2
3
4
5
3
aaa
12
aabaabaabaab
0
1
2
3
4
5
6
7
8
9
Test case #1
2 2
3 3

Test case #2
2 2 --aa(a)
6 2 --aabaab(aab)
9 3 --aabaabaab(aab)
12 4 --....

思路:求出Next数组后从1开始遍历,若$S[1-i]$是循环字符串则输出 $i$ 和 $N / len$

题解:

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
#include<bits/stdc++.h>
#define maxn 1000005
using namespace std;

int N, kase=0;
char s[maxn];
int Next[maxn];

void getnext()
{
Next[0] = -1;
int i = 0, j = -1;
while(i<N)
{
while(j!=-1 && s[i]!=s[j]) j = Next[j];
Next[++i] = ++j;
}
printf("Test case #%d\n", ++kase);
for(int i=2;i<=N;i++)
{
if(Next[i]==0) continue;
int len = i - Next[i];
if(Next[i]%len==0) cout << i << ' ' << Next[i]/len+1 << endl;
}
putchar('\n');
}

int main()
{
scanf("%d", &N); getchar();
while(N)
{
gets(s);
getnext();
scanf("%d", &N); getchar();
}
return 0;
}


HUST-1010

对于字符串A, 将其重复多次,形成新的字符串AAA…AAAA,在其中截取一段,作为B.
现给定B字符串,求符合条件的最短的A

1
2
bcabcab
efgabcdefgabcde
1
2
3
7

思路:本题实际上就是在求B中的循环节长度(N-Next[N]),只不过前/后可以多/少一些部分,原来的方法依然是可求的。
代码略


HDU-3377

题意:字符串长度为n(n<=1000000),问从哪一个字符串开始的循环字符串是 最大/最小字符串,如果存在多个输出编号最小的,以及输出最大/最小字符串在其中出现的次数。
比如SKYLONG:

String Rank
SKYLONG 1
KYLONGS 2
YLONGSK 3
LONGSKY 4
ONGSKYL 5
NGSKYLO 6
GSKYLON 7

1
2
3
abcder
aaaaaa
ababab
1
2
3
1 1 6 1
1 6 1 6
1 3 2 3



题解: 最大/最小字符串涉及到一个”最大/最小表示法“的算法。第二个问,实际上就是在求循环节,因为本来都是循环字符串,所以循环节的个数就是出现的个数

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include<cstdio>
#include<iostream>
#include<queue>
#include<string>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#define maxn 10000005
using namespace std;

string s;

int Next[maxn];
int n;

void getnext()
{
Next[0] = -1;
int i = 0, j = -1;
while(i<n)
{
while(j!=-1 && s[i]!=s[j]) j = Next[j];
Next[++i] = ++j;
}
}

int GetMinPos(string x,int l)
{
int i,j,k;
i = 0,j = 1,k = 0;
while(i < l && j < l) {
k = 0;
while(x[(i+k)%l] == x[(j+k)%l] && k < l) k++;
if(k == l) break;
if(x[(i+k)%l] < x[(j+k)%l])
if(j+k+1 >= i) j += k+1;
else j = i+1;
else
if(i+k+1 >= j) i += k+1;
else i = j+1;
if(i == j) j++;
}
return min(i,j);
}

int GetMaxPos(string x, int l)
{
int i,j,k;
i = 0,j = 1;
while(i < l && j < l) {
k = 0;
while(x[(i+k)%l] == x[(j+k)%l] && k < l) k++;
if(k == l) break;
if(x[(i+k)%l] < x[(j+k)%l])
if(i+k+1 >= j) i += k+1;
else i = j+1;
else
if(j+k+1 >= i) j += k+1;
else j = i+1;
if(i == j) j++;
}
return min(i,j);
}



int main()
{
std::ios::sync_with_stdio(false); std::cin.tie(0); //用cin string不用这个会超时的,可以改char
while(cin >> s)
{
int ans;
n = s.size();
getnext();
int len = n - Next[n];
if(Next[n]==0 || n%len) ans = 1;
else if(n%len==0) ans = n/len;

printf("%d %d %d %d\n", GetMinPos(s,n)+1, ans, GetMaxPos(s, n)+1, ans);
}
return 0;
}
文章作者: Irimsky
文章链接: /2019/11/05/KMP-循环节问题/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Irimsky's Blog

评论