0%

题意:给出两个数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);
}
}

HDU Count the string (KMP)

题意:给定一字符串,求它所有的前缀出现的次数的和。

思路: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) { //p[k]表示前缀,p[j]表示后缀
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
//优化过后的next 数组求法  
void GetNextval(char* p, int next[]) {
int pLen = strlen(p);
next[0] = -1;
int k = -1, j = 0;
while (j < pLen - 1) {
//p[k]表示前缀,p[j]表示后缀
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) {
//①如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),都令i++,j++
if (j == -1 || s[i] == p[j]) {
i++; j++;
} else {
//②如果j != -1,且当前字符匹配失败(即S[i] != P[j]),则令 i 不变,j = next[j]
//next[j]即为j所对应的next值
j = next[j];
}
}
if (j == pLen) {
return i - j;
} else {
return -1;
}
}

有一个小地方需要注意一下:

就是next数组,最好换一个名字,有可能会导致编译过不了~