http://acm.hdu.edu.cn/showproblem.php?pid=2846
题意：给出N个模式串，再给出M个文本串，问每一个文本串在多少个模式串中出现。
思路：平时都是找前缀的，这里将模式串s[1……len]的每一个[i,len]的子串都插入，这样就可以满足条件。还要注意如果两个子串都为同一个模式串的子串，不能重复计数。可以用一个id数组装上一次是哪个串的id，如果id相同就不要重复计数了。
1 #include <cstdio> 2 #include <algorithm> 3 #include <iostream> 4 #include <cstring> 5 #include <string> 6 #include <cmath> 7 #include <queue> 8 #include <vector> 9 using namespace std; 10 #define N 2000010 11 char s[25]; 12 struct Trie 13 { 14 int ch[N][26], num, cnt[N], id[N]; //空间尽量开大点 15 16 void init() 17 { 18 memset(ch[0], 0, sizeof(ch[0])); 19 num = 1; 20 } 21 22 void update(char *s, int index) 23 { 24 int u = 0; 25 int len = strlen(s); 26 for(int i = 0; i < len; i++) { 27 int tmp = s[i] - 'a'; 28 if(!ch[u][tmp]) { 29 memset(ch[num], 0, sizeof(ch[num])); 30 cnt[num] = 0; 31 id[num] = 0; 32 ch[u][tmp] = num++; 33 } 34 u = ch[u][tmp]; 35 if(id[u] != index) cnt[u]++; 36 id[u] = index; //标记上一个是否是相同的串,如果相同不能重复计数 37 } 38 } 39 40 int query(char *s) 41 { 42 int u = 0; 43 int len = strlen(s); 44 for(int i = 0; i < len; i++) { 45 int tmp = s[i] - 'a'; 46 if(!ch[u][tmp]) return 0; 47 u = ch[u][tmp]; 48 } 49 return cnt[u]; 50 } 51 }trie; 52 53 int main() 54 { 55 int n; 56 scanf("%d", &n); 57 trie.init(); 58 for(int i = 1; i <= n; i++) { 59 scanf("%*c%s", s); 60 int len = strlen(s); 61 for(int j = 0; j < len; j++) { 62 trie.update(s + j, i); //每一个串的以s[j]开头的子串都要插入 63 } 64 } 65 scanf("%d", &n); 66 for(int i = 0; i < n; i++) { 67 scanf("%*c%s", s); 68 printf("%d ", trie.query(s)); 69 } 70 return 0; 71 }