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