本文共 3107 字，大约阅读时间需要 10 分钟。
给定n个字符串Ai
给定m个字符串Bi
问所有的Bi在每个Ai中出现了多少次
很显然，对Bi建Trie图，然后每次用Ai去匹配的时候，不断查找当前匹配串的最长后缀，这样就能找到答案了
比赛的时候也这样水过了。（又一次我认为这样不会过，但是交上去却过了）
如有有这样的数据的话
1
1 1
10^5个a
那么时间复杂度是10^10,
其实上面不断查找当前匹配串的最长后缀是没必要的，是重复操作的。
如果我们知道当前匹配串的最长后缀包含了多少个Bi，那么就不用去不断回溯了。
所以我们只要在构建fail指针的时候，处理处当前fail指针指向的字符串包含了多少个Bi，那么就不用不断的回溯了。
（哈哈，学到东西了）
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std; 14 #pragma warning(disable:4996) 15 #pragma comment(linker, "/STACK:1024000000,1024000000") 16 typedef long long LL; 17 const int INF = 1<<30; 18 /* 19 20 */ 21 const int N = 1000000 + 10; 22 struct Node 23 { 24 int fail, next[26]; 25 int cnt; 26 void init() 27 { 28 fail = -1; 29 cnt = 0; 30 for (int i = 0; i < 26; ++i) 31 next[i] = -1; 32 } 33 }Trie[N]; 34 int size; 35 void insert(int root, char *str) 36 { 37 int idx, cur = root; 38 for (int i = 0; str[i]; ++i) 39 { 40 idx = str[i] - 'a'; 41 if (Trie[cur].next[idx] == -1) 42 { 43 Trie[size].init(); 44 Trie[cur].next[idx] = size++; 45 } 46 cur = Trie[cur].next[idx]; 47 } 48 Trie[cur].cnt++; 49 } 50 void makeFail(int root) 51 { 52 queue q; 53 for (int i = 0; i < 26; ++i) 54 { 55 if (Trie[root].next[i] == -1) 56 Trie[root].next[i] = root; 57 else 58 { 59 Trie[Trie[root].next[i]].fail = root; 60 q.push(Trie[root].next[i]); 61 } 62 } 63 while (!q.empty()) 64 { 65 int cur = q.front(); 66 q.pop(); 67 for (int i = 0; i < 26; ++i) 68 { 69 if (Trie[cur].next[i] == -1) 70 { 71 Trie[cur].next[i] = Trie[Trie[cur].fail].next[i]; 72 } 73 else 74 { 75 Trie[Trie[cur].next[i]].fail = Trie[Trie[cur].fail].next[i]; 76 //处理处，当前fail指针指向的字符串包含了多少个Bi 77 Trie[Trie[cur].next[i]].cnt += Trie[Trie[Trie[cur].fail].next[i]].cnt; 78 q.push(Trie[cur].next[i]); 79 } 80 81 } 82 } 83 } 84 int match(int root, char *str) 85 { 86 int i = 0; 87 int idx; 88 int cur = root; 89 int ret = 0; 90 while (str[i]) 91 { 92 idx = str[i] - 'a'; 93 cur = Trie[cur].next[idx]; 94 //int tmp = cur; 95 //while (tmp != root) 96 //{ 97 // ret += Trie[tmp].cnt; 98 // tmp = Trie[tmp].fail; 99 //}100 101 ret += Trie[cur].cnt;102 i++;103 }104 return ret;105 }106 /*107 题目问所有的Bi在每一个Ai中出现的次数108 109 一个串的所有子串可以表示为它所有前缀的后缀110 对所有的Bi建trie图111 我们可以让每个Ai匹配的时候，就让这个当前字符串不断的去寻找最长后缀，112 时间复杂度吵了113 ，然而数据水，居然过了114 */115 116 char str[666666];117 char str2[666666];118 int main()119 {120 int t, n, m;121 //freopen("d:/in.txt", "r", stdin);122 scanf("%d", &t);123 while (t--)124 {125 scanf("%d%d", &n, &m);126 int idx = 0;127 size = 1;128 Trie[0].init();129 Trie[0].fail = 0;130 for (int i = 0; i < n; ++i)131 {132 scanf("%s", str + idx);133 idx += strlen(str + idx) + 1;134 }135 for (int i = 0; i < m; ++i)136 {137 scanf("%s", str2);138 insert(0,str2);139 }140 makeFail(0);141 idx = 0;142 for (int i = 0; i < n; ++i)143 {144 printf("%d\n", match(0, str + idx));145 idx += strlen(str + idx) + 1;146 }147 }148 return 0;149 }
转载于:https://www.cnblogs.com/justPassBy/p/4728613.html
