KMP题目总结1——2014.4

本文从WordPress迁移而来, 查看全部WordPress迁移文章

HDU 3336 Count the string

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
/* 
题意:统计一个串的每一个前缀在该串中出现了多少次
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAX 200010
#define MOD 10007

char t[MAX];
int len,next[MAX],cnt[MAX];

int countPrefix_T(){
memset(cnt,0,sizeof(cnt));
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1) ++i , ++j;
else if(t[j] == t[i]) cnt[j]++ , ++i , ++j , next[i] = j;
else j = next[j];
}
for(int i = len; i > 1; i--)
cnt[next[i]-1] += cnt[i-1];
int sum = 0;
for(int i = 0; i < len; i++){
cnt[i]++;
sum += cnt[i];
sum %= MOD;
}
//for(int i = 0; i < len; i++)
// printf("%d : %d\n",i,cnt[i]);
return sum;
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%s",&len,t);
cout << countPrefix_T() << endl;
}
return 0;
}

HDU 3746 Cyclic Nacklace

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
/*
题意:一个字符串,要让它变成一个循环的字符串(至少循环两次),添加最少的字符串
aaa,循环节是a,已经循环3次,不需要添加任何字符
abcd,循环节就是abcd,添加至两次,变成abcdabcd
abcabca,这种,循环节是abc,但是最后一个不够,要添加bc,变成abcabcabc

这题的话,就是next的性质的
忘记哪题里面学到的一个知识点

pre = len - next[len] , 就是这段前缀,是可以循环覆盖整个字符串的
如果 len % pre == 0,那么pre刚好就是循环节
例如 aaaa,len = 4,next[len] = 3,pre = len-next[len] = 1, 前缀a就是整个串的循环节
如果 len % pre != 0, 整个字符串就不是一个循环字符串,但,这个字符串还是可以用pre来覆盖的(只是最后那段有多出来的部分)
例如 aabcaa,len = 6 , next[len] = 2 , pre = len-next[len] = 4,整个在字符串是可以用 aabc来覆盖的,最后会多出来bc

所以对于原串,求出 pre
1.pre = len,那么这个串无任何公共前缀,后缀,把整个串重复一次即可
2.pre刚好能被len整除,那么就是个循环字符串,不需要添加任何东西
3.否则,就以pre为循环节,把齐这个串,上面的例如,aabcaa,pre=aabc,补齐这个串,就是aabcaabc
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
using namespace std;
#define MAX 100010

char a[MAX];
int lena,nexta[MAX];
char b[MAX<<1];
int lenb,nextb[MAX<<1];

void getNext(char *t,int *next,int len){
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || t[i] == t[j]) { ++i; ++j; next[i] = j; }
else j = next[j];
}
}

void createString(char *s,char *t,int *next,int lent,int ret){
int i = lent,j = lent-lent/ret*ret;
strcpy(s,t);
for( ; j < ret; i++,j++)
s[i] = t[j];
s[i] = '\0';
//puts(s);
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%s",a);
lena = strlen(a);
getNext(a,nexta,lena);
int rea = lena - nexta[lena];
if(rea == lena){
printf("%d\n",lena); continue;
}
if(lena % rea == 0){
printf("%d\n",0); continue;
}
createString(b,a,nexta,lena,rea);
int lenb = strlen(b);
getNext(b,nextb,lenb);
int reb = lenb - nextb[lenb];
printf("%d\n",reb-(lena-lena/rea*rea));
}
return 0;
}

HDU 1358 Period

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAX 1000010

char t[MAX];
int len,nextT[MAX];

void getNext(char *t,int *next){
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || t[i] == t[j]){ ++i; ++j; next[i] = j; }
else j = next[j];
}
}

int main(){
int cas = 0;
while(scanf("%d",&len)!=EOF && len){
scanf("%s",t);
getNext(t,nextT);
printf("Test case #%d\n",++cas);
for(int i = 2; i <= len; i++){
if((i % (i-nextT[i])) == 0 && nextT[i]!=0) printf("%d %d\n",i,i/(i-nextT[i]));
}
puts("");
}
return 0;
}

HDU 1358 Period

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
/*
给一个串,对于每个前缀,都看看它是不是一个有循环节的字符串,是的话,输出这个前缀以及这个前缀循环了几次
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAX 1000010

char t[MAX];
int len,nextT[MAX];

void getNext(char *t,int *next){
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || t[i] == t[j]){ ++i; ++j; next[i] = j; }
else j = next[j];
}
}

int main(){
int cas = 0;
while(scanf("%d",&len)!=EOF && len){
scanf("%s",t);
getNext(t,nextT);
printf("Test case #%d\n",++cas);
for(int i = 2; i <= len; i++){
if((i % (i-nextT[i])) == 0 && nextT[i]!=0) printf("%d %d\n",i,i/(i-nextT[i]));
}
puts("");
}
return 0;
}

HDU 2087 剪花布条

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
/*
题意:不可重叠的多重匹配
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
#define MAX 1010

class KMP{
//s串和t串下标均从0开始
public:
char s[MAX],t[MAX];
int lens,lent,next[MAX];
int save[MAX],ns;
void init(char *ss,char *tt){
ns = 0;
lens = strlen(ss);
lent = strlen(tt);
for(int i = 0; ss[i]; i++) s[i] = ss[i];
for(int i = 0; tt[i]; i++) t[i] = tt[i];
s[lens] = t[lent] = '\0';
}
void getNext(){
int i = 0 , j = -1;
next[0] = -1;
while(i < lent){
if(j == -1 || t[i] == t[j]){ ++i; ++j; next[i] = j; }
else j = next[j];
}
}
//一次匹配,从st到ed-1位置,默认位置为st=0,ed=lens
int indexMP(int st,int ed){
int i = st , j = 0;
while(i < ed){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
}
if(j >= lent) return i-lent;
else -1;
}
//多次匹配(可重叠),把每个匹配的位置保存在save中,ns是成功匹配的次数
int multiIndexKMP(int st,int ed){
int i = st , j = 0;
while(i < ed){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
if(j == lent) { j = next[j]; save[ns++] = i-lent; }
}
return ns;
}
//多次匹配(不重叠),把每个匹配的位置保存在save中,ns是成功匹配的次数
int multiIndexKMP__(int st,int ed){
int i = st,j = 0;
while(i < ed){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
if(j == lent) { j = 0; save[ns++] = i-lent; }
}
return ns;
}

};

char s[MAX],t[MAX];

int main(){
KMP *kmp = new KMP();
while(scanf("%s",s)!=EOF && strcmp(s,"#")){
scanf("%s",t);
kmp->init(s,t);
kmp->getNext();
printf("%d\n",kmp->multiIndexKMP__(0,kmp->lens));
}
return 0;
}

HDU 2594 Simpsons’ Hidden Talents

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
/*
题意:给两个串a,b,求a的一个最长的前缀跟b的后缀相同
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAX 100010

char a[MAX],b[MAX];
int len,lena,lenb,nexta[MAX];

void getNext(char *t,int *next){
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || t[i] == t[j]) { ++i; ++j; next[i] = j; }
else j = next[j];
}
}

int main(){
while(scanf("%s",a)!=EOF){
scanf("%s",b);
lena = strlen(a);
lenb = strlen(b);
strcat(a,b);
len = strlen(a);
getNext(a,nexta);
nexta[len] = min(nexta[len],min(lena,lenb));
if(nexta[len] == 0) puts("0");
else{
for(int i = 0; i < nexta[len]; i++)
printf("%c",a[i]);
printf(" %d\n",nexta[len]);
}
}
return 0;
}

HDU 2203 亲和串

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
/*
题意:给两个串a,b,a串可以循环移位,使得b是a的一个子串;如果怎样循环移位都不行,输出no
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
#define MAX 1000010

class KMP{
//s串和t串下标均从0开始
public:
char s[MAX],t[MAX];
int lens,lent,next[MAX];
int save[MAX],ns;
void init(char *ss,char *tt){
ns = 0;
lens = strlen(ss);
lent = strlen(tt);
for(int i = 0; ss[i]; i++) s[i] = ss[i];
for(int i = 0; tt[i]; i++) t[i] = tt[i];
s[lens] = t[lent] = '\0';
}
void getNext(){
int i = 0 , j = -1;
next[0] = -1;
while(i < lent){
if(j == -1 || t[i] == t[j]){ ++i; ++j; next[i] = j; }
else j = next[j];
}
}
//一次匹配,从st到ed-1位置,默认位置为st=0,ed=lens
int indexMP(int st,int ed){
int i = st , j = 0;
while(i < ed && j < lent){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
}
if(j >= lent) return i-lent;
else return -1;
}
//多次匹配(可重叠),把每个匹配的位置保存在save中,ns是成功匹配的次数
int multiIndexKMP(int st,int ed){
int i = st , j = 0;
while(i < ed){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
if(j == lent) { j = next[j]; save[ns++] = i-lent; }
}
return ns;
}
//多次匹配(不重叠),把每个匹配的位置保存在save中,ns是成功匹配的次数
int multiIndexKMP__(int st,int ed){
int i = st,j = 0;
while(i < ed){
if(j == -1 || s[i] == t[j]){ ++i; ++j; }
else j = next[j];
if(j == lent) { j = 0; save[ns++] = i-lent; }
}
return ns;
}
};

char s[MAX],ss[MAX],t[MAX];

int main(){
KMP *kmp = new KMP();
while(scanf("%s",s)!=EOF){
scanf("%s",t);
strcpy(ss,s);
strcat(s,ss);
kmp->init(s,t);
kmp->getNext();
int pos = kmp->indexMP(0,kmp->lens);
if(pos == -1) puts("no");
else puts("yes");
}
return 0;
}

HDU 1867 A + B for you again

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
/*
题意:给两个串a,b,拼接两个串(a在前b在后),但是如果a串的后缀和b串的前缀相同,这部分可以抵消掉(只留一部分)
例如:asdf sdfg = asdfg
方法二:
要算A+B的拼接结果,将B放前,A放后,求一次next,总长度是len=lena+lenb
这样求出来的,就是 next[len] = 最长前缀=最后后缀
但是注意一种情况
A = aaaa
B = aa
最长匹配长度应该是2,但next[len] = 5
所以最长匹配长度应该满足 min(next[len],min(lena,lenb))
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define MAX 100010

class KMP{
public:
char t[MAX<<1];
char s[MAX<<1];
int len1,len2,len,next[MAX<<1];

void reset(char *a,char *b){
len1 = strlen(a);
len2 = strlen(b);
len = len1+len2;
for(int i = 0; i < len2; i++) t[i] = b[i];
for(int i = 0; i < len1; i++) t[i+len2] = a[i];
t[len1+len2] = '\0';
}

void getNext(){
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || t[i] == t[j]) { ++i; ++j; next[i] = j; }
else j = next[j];
}
}

void solve(){
getNext();
int maxLen = min(next[len],min(len1,len2));
//cout << maxLen << endl;
for(int i = 0; i < len1; i++) s[i] = t[i+len2];
for(int i = len1,j = maxLen;j < len2;i++,j++) s[i] = t[j];
s[len1+len2-maxLen] = '\0';
len = len1 + len2 - maxLen;
//puts(s);
}
}*A,*B;

char s[MAX],t[MAX];

KMP * cmp(KMP *a,KMP *b){
if(a->len < b->len ||
(a->len == b->len && strcmp(a->s,b->s) <= 0)) return a;
else return b;
}

int main(){

//freopen("case.txt","r",stdin);
//freopen("me.txt","w",stdout);

A = new KMP();
B = new KMP();
while(scanf("%s",s)!=EOF){
scanf("%s",t);
A->reset(s,t);
B->reset(t,s);
A->solve();
B->solve();
printf("%s\n",cmp(A,B)->s);
}
delete A;
delete B;
return 0;
}

UVA 11475 Extend to Palindrome

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
/*
题意:给定一个串,使其变为回文串,输出最短的回文串
要让最后的回文串最短的话,要充分利用给出来的串
假设给出来的串s,取一段后缀,把它反过来,还跟原来的后缀一模一样,那么我们只需要把
s-后缀 这一部分,翻转,加到s后面,s就能成为一个回文串了,加得越少,s越短,这就要求
符合要求的后缀越长越好
怎么求这样的后缀呢?
将整个串反过来,去和s匹配,因为这个串和s长度是一样的,无论怎样,都是s先走完
当s走完的时候,t走到了哪里,说明就是t的前缀有多少是和s的后缀匹配的
这就是我们要的最大长度
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAX 100010

char s[MAX<<1],t[MAX];
int len,nextT[MAX];

void getNext(char *t,int *next){
int i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || t[i] == t[j]) { ++i; ++j; next[i] = j; }
else j = next[j];
}
}

int indexKMP(char *s,char *t,int *next){
int i = 0 , j = 0,maxLen = 0;
while(i < len && j < len){
if(j == -1 || s[i] == t[j]){
++i; ++j;
}
else j = next[j];
}
return j;
}

int main(){
while(scanf("%s",s)!=EOF){
len = strlen(s);
for(int i = 0,j = len-1; i < len; i++,j--)
t[j] = s[i];
t[len] = '\0';
getNext(t,nextT);
int maxLen = indexKMP(s,t,nextT);
for(int i = len,j = len-maxLen-1; j >= 0; i++,j--)
s[i] = s[j];
s[len+len-maxLen] = '\0';
puts(s);
}
return 0;
}

UVA 12604 Caesar Cipher

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
/*
题意:讲的是恺撒密码,可以搜索一下什么是恺撒密码
每组case,第一行是单词表,第二行是要匹配的单词,第三行是密文
找出所有可能的偏移量,使得明文中只包含一个单词,输出所有的偏移量
对于恺撒密码
单词表 :abc
如果偏移一位 cab
对照着
abc
cab

明文是bbb的话,密文就是aaa
明文是bab的话,密文就是aca

现在给了密文,我们只要每次枚举一个偏移量,就能得到明文
得到明文后,就看明文有多少个单词,是可以重叠的,例如
单词 aba
明文 ababa
这样算有2个单词
为了提高速度,一旦匹配到2个了,就马上跳出
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define MAXA 65
#define MAXW 50010
#define MAXS 5000010

char a[MAXA],w[MAXW],s[MAXS],ss[MAXS];
int lena,lenw,lens,nextw[MAXW],Index[256];
int na,ans[MAXA],ns,save[MAXS];

void getNext(char *t,int *next){
int len = lenw,i = 0 , j = -1;
next[0] = -1;
while(i < len){
if(j == -1 || t[i] == t[j]) { ++i; ++j; next[i] = j; }
else j = next[j];
}
}

//多次匹配(可重叠),把每个匹配的位置保存在save中,ns是成功匹配的次数
int multiIndexKMP(char *s,int st,int ed,int *next){
int i = st , j = 0;
while(i < ed && ns < 2){
if(j == -1 || s[i] == w[j]){ ++i; ++j; }
else j = next[j];
if(j == lenw) { j = next[j]; save[ns++] = i-lenw; }
}
return ns;
}

inline void make(int d){
for(int i = 0; i < lens; i++){
int id = (Index[s[i]]-d+lena)%lena;
ss[i] = a[id];
}
ss[lens] = '\0';
//puts(ss);
}

void solve(){
na = 0;
int lena = strlen(a);
for(int delta = 0; delta < lena; delta++){
make(delta);
ns = 0;
multiIndexKMP(ss,0,lens,nextw);
if(ns == 1) ans[na++] = delta;
}

}

int main(){
int T;
scanf("%d",&T);
while(T--){
memset(Index,-1,sizeof(Index));
scanf("%s",a);
lena = strlen(a);
for(int i = 0; a[i]; i++) Index[a[i]] = i;
scanf("%s",w);
lenw = strlen(w);
getNext(w,nextw);
scanf("%s",s);
lens = strlen(s);
solve();
if(na == 0) puts("no solution");
else if(na == 1) printf("unique: %d\n",ans[0]);
else{
printf("ambiguous:");
for(int i = 0; i < na; i++) printf(" %d",ans[i]);
puts("");
}
}
return 0;
}