poj 1200 Crazy Search

　　字符串搜索，要将字符串之前搜索过的字符串用一个数来映射储存。这里的字符串长达16*10^6，所以不能hash储存，就连下标都不能存下来，所以这里不能用KR算法，因为KR算法要在找到相同以后还要再逐个比较。

　　这题的数据也比较水，m^n<10^7，所以可以直接开bool数组来记录字符串是否出现！

代码如下：

View Code

 1 #include <cstring>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <algorithm>
 5 
 6 using namespace std;
 7 
 8 typedef long long ll;
 9 const int maxn = 16000027;
10 bool vis[maxn >> 1];
11 char hash[128];
12 char buf[maxn];
13 
14 int deal(int n, int m) {
15     int len = strlen(buf);
16     int cnt = 0;
17     char c;
18 
19     if (len < n) return 0;
20     memset(hash, -1, sizeof(hash));
21     //memset(vis, false, sizeof(vis));
22 
23     int hi = 1, cur = 0;
24     int ret = 0;
25 
26     for (int i = 1; i < n; i++) {
27         hi *= m;
28     }
29     for (int i = 0; i < n - 1; i++) {
30         c = buf[i];
31 
32         if (hash[c] == -1) hash[c] = cnt++;
33         cur = cur * m + hash[c];
34     }
35     for (int i = n - 1; i < len; i++) {
36         c = buf[i];
37 
38         if (hash[c] == -1) hash[c] = cnt++;
39         cur = cur * m + hash[c];
40 //        cout << cur << endl;
41         if (!vis[cur]) vis[cur] = true, ret++;
42         cur -= hash[buf[i - n + 1]] * hi;
43     }
44 
45     return ret;
46 }
47 
48 
49 int main() {
50     int n, m;
51 
52     while (~scanf("%d%d", &n, &m)) {
53         scanf("%s", buf);
54         printf("%d\n", deal(n, m));
55     }
56 
57     return 0;
58 }

——written by Lyon