KMP题目总结2——2014.4

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

Codeforces Round #117 (Div. 2) D

http://codeforces.com/problemset/problem/182/D

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
/*
题意:给a,b串,找出他们各自有哪些循环节,然后看看它们有哪些公共的循环节
例如
a = abab
b = ababab
对于a来讲,ab,abab都是a串的循环节
对于b来讲,ab,abab,ababab都是b串的循环节
所以他们公共的循环节是ab,abab,输出2

做法是kmp,循环节,那就利用性质了
pre = len - next[len]
如果len % pre == 0,pre这个前缀就是最小循环节,若 len % pre != 0 , 这个串的循环节只有它自己
如果a,b串的最小循环节不同的话,他们是不会有公共循环节的,直接0
一个串除了最小循环节,还有什么循环节?
假设有4个最小循环节,那么1,2,4个最小循环节循环节都可以是串的循环节
加入有15个最小循环节,那么1,3,5,15个最小循环节都可以是串的循环节
嗯,就是,找,约数的个数!
如果a串有ca个最小循环节,找出ca的所有约数
如果b串有cb个最小循环节,找出cb的所有约数
有多少个公共的约数,就是答案
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
#define MAX 100010
#define LL long long

char a[MAX],b[MAX],sa[MAX],sb[MAX];
int nextT[MAX];
int ca[MAX],cb[MAX];

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

void getString(char *s,char *subs){
int lens = strlen(s),plen = lens - nextT[lens],sublens = 0;
if(lens % plen != 0) sublens = lens;
else sublens = plen;
for(int i = 0; i < sublens; i++)
subs[i] = s[i];
subs[sublens] = '\0';

}

void solve(int n,int *cnt){
//memset(cnt,0,sizeof(cnt));
int lim = (int)sqrt(n+0.5);
for(int p = 2; p <= lim && n > 1; p++){
if(n % p == 0){
while(n % p == 0){ cnt[p]++; n /= p; }
}
}
if(n > 1) cnt[n]++;
}

LL work(){
LL ans = 1LL;
for(int i = 2; i <= 100000; i++){
int t = min(ca[i],cb[i]);
ans *= (t+1);
}
return ans;
}

int main(){
int ra,rb;
while(scanf("%s",a)!=EOF){
scanf("%s",b);
int lena = strlen(a) , lenb = strlen(b);
getNext(a,nextT);
getString(a,sa);

getNext(b,nextT);
getString(b,sb);

if(strcmp(sa,sb)) { puts("0"); continue; }

int lensa = strlen(sa) , lensb = strlen(sb);
int cnta = lena / lensa , cntb = lenb / lensb;

//printf("%d --- %d\n",cnta,cntb);

memset(ca,0,sizeof(ca));
memset(cb,0,sizeof(cb));

solve(cnta,ca);
solve(cntb,cb);
cout << work() << endl;
}
return 0;
}

POJ 2406 Power Strings

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

char T[MAX];
int nextT[MAX];
stack<int>sta;

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

int solve(){
int lenT = strlen(T);
if(nextT[lenT] == 0 || lenT%(lenT-nextT[lenT]) != 0)
return 1;
return lenT/(lenT-nextT[lenT]);
}

int main(){
while(scanf("%s",T)!=EOF){
if(!strcmp(T,".")) break;
getNext(T,nextT);
printf("%d\n",solve());
}
return 0;
}

poj 2541 Binary Witch

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
/*
题意:给一个字符串,找到一个子串,跟后缀相同(当然不能是后缀本身,但可以与后缀有重叠部分),后缀越长越好,长度相同时,越靠右越好,后缀的长度最长不超过13,找到子串后,取子串的下一位补在整个串的最后(如果找不到,则补0),接着以这个新串做相同的时候,一共做m次
要找最长的后缀,因为长度最多只有13,枚举后缀去匹配就行了,把整个串反过来看,就是个普通的KMP
只不过这题,每次加一个新字符后整个串都变了,要重新求一次next什么的,其实用KMP应该是会超时的
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define N 1000010
#define M 1010

int n,m,next[N+M];
char s[N+M];

void getNext(){
int i = n-1 , j = n;
next[n-1] = n;
while(i){
if(j == n || s[i] == s[j]) { --i; --j; next[i] = j; }
else j = next[j];
}
}

int IndexKMP(int st,int L){
int i = st, j = n-1,eds = 0,edt = n-L-1;
while(i > eds && j > edt){
if(j == n || s[i] == s[j]){ --i; --j; }
else j = next[j];
}
if(j == edt) return i+L;
return -1;

}

char find(){
for(int L = min(n-2,13); L; L--){
int index = IndexKMP(n-2,L);
if(index != -1) return s[index+1];
}
return '0';
}

int main(){
while(scanf("%d%d%s",&n,&m,s+1)!=EOF){
int end = n+m+1;
n++;
while(n <= end){
getNext();
s[n++] = find();
}
for(int i = end-m; i < end; i++)
printf("%c",s[i]);
puts("");
}
return 0;
}

ZOJ 3587 Marlon’s 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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/*
题意:给一个字符串,找到一个子串,跟后缀相同(当然不能是后缀本身,但可以与后缀有重叠部分),后缀越长越好,长度相同时,越靠右越好,后缀的长度最长不超过13,找到子串后,取子串的下一位补在整个串的最后(如果找不到,则补0),接着以这个新串做相同的时候,一共做m次
要找最长的后缀,因为长度最多只有13,枚举后缀去匹配就行了,把整个串反过来看,就是个普通的KMP
只不过这题,每次加一个新字符后整个串都变了,要重新求一次next什么的,其实用KMP应该是会超时的
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define LL long long
#define N 1000010
#define M 1010

int n,m,next[N+M];
char s[N+M];

void getNext(){
int i = n-1 , j = n;
next[n-1] = n;
while(i){
if(j == n || s[i] == s[j]) { --i; --j; next[i] = j; }
else j = next[j];
}
}

int IndexKMP(int st,int L){
int i = st, j = n-1,eds = 0,edt = n-L-1;
while(i > eds && j > edt){
if(j == n || s[i] == s[j]){ --i; --j; }
else j = next[j];
}
if(j == edt) return i+L;
return -1;

}

char find(){
for(int L = min(n-2,13); L; L--){
int index = IndexKMP(n-2,L);
if(index != -1) return s[index+1];
}
return '0';
}

int main(){
while(scanf("%d%d%s",&n,&m,s+1)!=EOF){
int end = n+m+1;
n++;
while(n <= end){
getNext();
s[n++] = find();
}
for(int i = end-m; i < end; i++)
printf("%c",s[i]);
puts("");
}
return 0;
}

ZOJ 3298 Crack

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
/*
题意:读懂题意就能做,就是按照题意去模拟
给一个t串,一个s串,如果在s中找不到一个t,输出bad
如果能找到,要找最长的,最长的意思是,可以继续扩展,循环扩展
例如 sample 2
3 8
1 3 2
2 3 2 1 3 2 1 5
在s中先找到了 1 3 2
然后向两头扩展,t串则循环去匹,直到不行为止

所以做法就很明显了,在s中匹配t,找出所有成功匹配整个t的位置
枚举这些位置,然后向两头扩展
枚举这里可以优化一下的,这个代码跑得比较慢
例如
1 1 1
1 1 1 1 1 1 1 1 1 1
这样的串,显然可以优化很多
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
#define MAXT 1010
#define MAXS 1000010

int t[MAXT],s[MAXS],next[MAXT],save[MAXS],ns,lent,lens;

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];
}
}

void multiIndexKMP(){
ns = 0;
int i = 0 , j = 0;
while(i < lens){
if(j == -1 || s[i] == t[j]) { ++i; ++j; }
else j = next[j];
if(j == lent) save[ns++] = i - lent;
}

//printf("ns = %d\n",ns);
//for(int i = 0; i < ns; i++)
//printf("%d%c",save[i],i == ns-1 ? '\n':' ');
}

int solve(){
int ans = 0;
for(int ith = 0; ith < ns; ith++){
int sum = 0,i = save[ith] - 1,j = lent - 1 ;
while(i >= 0 && s[i] == t[j])
sum++ , i-- , j = (j-1+lent)%lent;
i = save[ith] , j = 0;
while(i < lens && s[i] == t[j])
sum++ , i++ , j = (j + 1) % lent;
ans = max(ans,sum);
}
return ans;
}

int main(){
while(scanf("%d%d",&lent,&lens)!=EOF){
for(int i = 0 ; i < lent; i++)
scanf("%d",&t[i]);
for(int i = 0; i < lens; i++)
scanf("%d",&s[i]);
getNext();
multiIndexKMP();
if(ns) printf("%d\n",solve());
else puts("bad");
}
return 0;
}

zoj 3643 Keep Deleting

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
/*
一开始暴力kmp匹配,删除,合并,再匹配,超时
后来想一下,如果某一次匹配成功了,回到上一次的地方,例如
abc
ababcdd
匹配完abc后,回到ab的那个b那里

abc
ababcabcabcee
第一个abc成功后回到ab的b那里,
第二个abc成功后回到ab的b那里,
第三次abc成功后,回到ab的b那里,
思想是这样,也不难想,实现起来的话,我一开始想用一些索引去找到回去的位置
后来想想, 用栈的话,简单明了
注意些细节

Index数组可以省略,只是为了辅助理解, Index[i]是记录s[i]匹配到了哪个t[j]
*/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <stack>
using namespace std;
#define MAXS 512010
#define MAXT 310
#define pii pair<int,int>
#define mp make_pair

char s[MAXS],t[MAXT];
int lens,lent,nextT[MAXT],Index[MAXS];
stack<pii>sta;

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

void POP(int n){
while(n--) sta.pop();
}

int solve(){
while(!sta.empty()) sta.pop();
memset(Index,-1,sizeof(Index));
int i = 0 , j = 0 , ans = 0;
while(i < lens){
if(j == -1 || s[i] == t[j]){ Index[i] = j; sta.push(mp(i,j)); ++i; ++j; }
else j = nextT[j];
if(j == lent){
ans++;
if(i == lens) break;
POP(lent);
if(sta.empty()) continue;
else j = sta.top().second+1;
}
}
return ans;
}

int main(){
while(scanf("%s",t)!=EOF){
scanf("%s",s);
lent = strlen(t);
lens = strlen(s);
getNext();
printf("%d\n",solve());
}
return 0;
}

POJ 3080 Blue Jeans

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
/*
题意:给n(2<=n<=10)个串,每个长度固定是60,在这n个串里面,找到一个最长的公共子串,长度相同时要字典序最小
做法,枚举第一个串的子串,然后在其他串中匹配,能匹配成功的就是答案
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
using namespace std;
#define N 15
#define LEN 60

string s[N],substring,ans;
int n,next[LEN+10];

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

int indexKMP(int id,int L){
int i = 0 , j = 0;
while(i < LEN && j < L){
if(j == -1 || s[id][i] == substring[j]) { ++i; ++j; }
else j = next[j];
}
if(j >= L) return i-L;
else return -1;
}

void solve(){
for(int L = LEN; L > 2; L--){
bool flag = false;
for(int i = 0; i+L <= LEN; i++){
bool res = true;
substring = s[0].substr(i,L);
//cout << substring << endl;
getNext();
for(int i = 1; i < n; i++)
if(indexKMP(i,L) == -1) { res = false; break; }
if(!res) continue;
else{ flag = true; ans = min(ans,substring); }
}
if(flag) return;
}
}

int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i = 0 ; i < n; i++)
cin >> s[i];
ans = "Z";
solve();
if(ans == "Z") cout << "no significant commonalities" << endl;
else cout << ans << endl;
}
return 0;
}

POJ 3450 Corporate Identity

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
/*
题意:给n(2<=n<=10)个串,每个长度固定是60,在这n个串里面,找到一个最长的公共子串,长度相同时要字典序最小
做法,枚举第一个串的子串,然后在其他串中匹配,能匹配成功的就是答案
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <string>
using namespace std;
#define N 4010
#define MAXLEN 210

string s[N],substring,ans;
int n,next[MAXLEN];

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

int indexKMP(int id,int L){
int i = 0 , j = 0 , lens = s[id].length();
while(i < lens && j < L){
if(j == -1 || s[id][i] == substring[j]) { ++i; ++j; }
else j = next[j];
}
if(j >= L) return i-L;
else return -1;
}

void solve(){
int LEN = s[0].length();
for(int L = LEN; L; L--){
bool flag = false;
for(int i = 0; i+L <= LEN; i++){
bool res = true;
substring = s[0].substr(i,L);
//cout << substring << endl;
getNext(L);
for(int i = 1; i < n; i++)
if(indexKMP(i,L) == -1) { res = false; break; }
if(!res) continue;
else{ flag = true; ans = (ans == "" ? substring : min(ans,substring)); }
}
if(flag) return;
}
}

bool CMP(string x,string y){
return x.length() < y.length();
}

int main(){
while(scanf("%d",&n)!=EOF && n){
for(int i = 0 ; i < n; i++)
cin >> s[i];
sort(s,s+n,CMP);
ans = "";
solve();
if(ans == "") cout << "IDENTITY LOST" << endl;
else cout << ans << endl;
}
return 0;
}