POJ 1200 Crazy Search
题意：给出两个数n,nc，并给出一个由nc种字符组成的字符串。求这个字符串中长度为n的不同子串有多少种？
思路：
**Hash！**将长度为n的子串看作n位的nc进制数，将问题转化为共有多少种十进制数字。哈希时，每一个字符都对应这0~ nc-1的一个数字
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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 16000005;
char str[MAXN];
int hash[MAXN];
int asc[256];
int main() {
int n, m;
while(scanf("%d%d", &n, &m) != EOF) {
memset(asc, 0, sizeof(asc));
memset(hash, 0, sizeof(hash));
scanf("%s", str);
int len = 0;
int stlen = strlen(str);
for(int i = 0; i < stlen && len < m; i++) {
if(asc[str[i]] == 0) {
asc[str[i]] = len++;
}
}
int tot = 0;
stlen = stlen - n + 1;
for(int i = 0; i < stlen; i++) {
int sum = 0;
for(int j = 0; j < n; j++) {
sum = sum * m + asc[str[j + i]];
}
if(hash[sum] == 0) {
hash[sum] = 1;
tot++;
}
}
printf("%d\n", tot);
}
}
|
题意：给定一字符串，求它所有的前缀出现的次数的和。
思路：KMP + dp
问题可以转化为，求以i结尾的字符串所包含的前缀的个数
定义状态dp[i]表示前缀i所包含的前缀的个数，考虑转移，借助KMP的next数组
前缀i所包含的最长的前缀的长度为next[i]，在next[i]+1~i之间的前缀没有
故dp[i] = dp[next[i]] + 1，递推即可。
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
| #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = (int)2e5+5;
const int mod = 10007;
int prefix[MAXN], dp[MAXN];
string pattern;
int length;
void get_prefix_table() {
int i = 0, len = -1;
prefix[0] = -1;
while(i < length) {
if(len == -1 || pattern[i] == pattern[len]) {
++i; ++len;
prefix[i] = len;
} else {
len = prefix[len];
}
}
return ;
}
void solve() {
int sum = 0;
get_prefix_table();
memset(dp, 0, sizeof(dp));
dp[0] = 0;
for(int i = 1; i <= length; i++) {
dp[i] = (dp[prefix[i]] + 1) % mod;
sum = (sum + dp[i]) % mod;
}
printf("%d\n", sum);
return ;
}
int main() {
ios::sync_with_stdio(false);
int n;
scanf("%d", &n);
for(int i = 0; i < n; i++) {
cin >> length >> pattern;
solve();
}
}
|
补充KMP算法
未优化前的求解next数组
1
2
3
4
5
6
7
8
9
10
11
12
13
| void GetNext(char* p,int next[]) {
int pLen = strlen(p);
next[0] = -1;
int k = -1, j = 0;
while(j < pLen - 1) {
if(k == -1 || p[j] == p[k]) {
++k; ++j;
next[j] = k;
} else {
k = next[k];
}
}
}
|
优化后的next数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
void GetNextval(char* p, int next[]) {
int pLen = strlen(p);
next[0] = -1;
int k = -1, j = 0;
while (j < pLen - 1) {
if (k == -1 || p[j] == p[k]) {
++j; ++k;
if (p[j] != p[k]) {
next[j] = k;
} else {
next[j] = next[k];
}
} else {
k = next[k];
}
}
}
|
KMP
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| int KMPSearch(char* s, char* p) {
int i = 0, j = 0;
int sLen = strlen(s);
int pLen = strlen(p);
while (i < sLen && j < pLen) {
if (j == -1 || s[i] == p[j]) {
i++; j++;
} else {
j = next[j];
}
}
if (j == pLen) {
return i - j;
} else {
return -1;
}
}
|
有一个小地方需要注意一下：
就是next数组，最好换一个名字，有可能会导致编译过不了~