首页 > 代码库 > POJ 4052 AC自动机
POJ 4052 AC自动机
【题意】：
给你n个字符串和一个文本，问有多少个字符串满足如下条件：该字符串包含在文本，该字符串不为其它字符串的子串。
【知识点】：
Ac自动机，处理字符串
【题解】：
集训比赛的时候当时被题目的数据量吓到了，不敢用ac自动机。但在网上看到题解时，然后瞬间就感觉自己想多了。。。
很水的一道ac自动机处理字符串的题目，先将查询的字符做成字典树，然后在文本中查找字符串是否存在。
在处理去子串上，我的做法是查找文本时去除后缀相同的包含子串。然后单独在搜索剩余可用字符串前缀相同子串。
【代码】：
1 #include <map> 2 #include <set> 3 #include <cmath> 4 #include <ctime> 5 #include <queue> 6 #include <stack> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstring> 11 #include <sstream> 12 #include <iostream> 13 #include <algorithm> 14 #include <bitset> 15 #include <climits> 16 using namespace std; 17 18 #define wh while 19 #define inf (int)(~0u/2) 20 #define FOR(i, n) for(int i = 0; i < n; i++) 21 #define FOR1(i, n) for(int i = 1; i < n; i++) 22 #define FOR2(i, n) for(int i = 0; i <= n; i++) 23 #define REP(i,n) for(int i = 1; i <= n; i++) 24 #define FORI(it,n) for(typeof(n.begin()) it = n.begin(); it != n.end(); it++) 25 #define sf scanf 26 #define pf printf 27 #define frs first 28 #define sec second 29 #define psh push_back 30 #define mkp make_pair 31 #define PB(x) push_back(x) 32 #define MP(x, y) make_pair(x, y) 33 #define clr(abc,z) memset(abc,z,sizeof(abc)) 34 #define lt(v) v << 1 35 #define rt(v) v << 1 | 1 36 #define mid ((l + r) >> 1) 37 #define lson l, mid, v << 1 38 #define rson mid + 1, r, v << 1 | 1 39 40 #define fre freopen("1.txt", "r", stdin) 41 42 typedef long long LL; 43 typedef long double LD; 44 45 const int maxn = 3000; 46 const int maxlen = 1300; 47 const int maxlen2 = 3e6 + 10; 48 char st[maxn][maxlen]; 49 char ctmp[maxlen2 * 2]; 50 char text[maxlen2 * 2]; 51 bool vis[maxn]; 52 53 const int SIGMA_SIZE = 26; 54 const int MAXNODE = 3e6 + 10; 55 const int MAXS = 150 + 10; 56 57 char* deal(char* res, char* s){ 58 int len = 0; int t = 0; 59 for(int i = 0; s[i]; i++){ 60 if(s[i] == ‘[‘ || s[i] == ‘]‘) t = 0; 61 else if(s[i] >= 0 && s[i] <= ‘9‘) t = t * 10 + s[i] - ‘0‘; 62 else if(s[i] >= ‘A‘ && s[i] <= ‘Z‘){ 63 if(t == 0) 64 res[len++] = s[i]; 65 else{ 66 while(t--) 67 res[len++] = s[i]; 68 } 69 } 70 } 71 res[len] = ‘\0‘; 72 return res; 73 } 74 struct AhoCorasickAutomata { 75 int ch[MAXNODE][SIGMA_SIZE]; 76 int f[MAXNODE]; 77 int val[MAXNODE]; 78 int last[MAXNODE]; 79 int sz; 80 void init() { 81 sz = 1; 82 memset(ch[0], 0, sizeof(ch[0])); 83 } 84 int idx(char c) { 85 return c - ‘A‘; 86 } 87 void _insert(char *s, int v) { 88 int u = 0, n = strlen(s); 89 for(int i = 0; i < n; i++) { 90 int c = idx(s[i]); 91 if(!ch[u][c]) { 92 memset(ch[sz], 0, sizeof(ch[sz])); 93 val[sz] = 0; 94 ch[u][c] = sz++; 95 } 96 u = ch[u][c]; 97 } 98 val[u] = v; 99 }100 void doA(int j) {101 if(j) {102 vis[val[j]] = true;103 }104 }105 void doB(int j) {106 if(j) {107 vis[val[j]] = false;108 doB(last[j]);109 }110 }111 void _find(char* T) {112 int n = strlen(T);113 int j = 0;114 for(int i = 0; i < n; i++) {115 int c = idx(T[i]);116 while(j && !ch[j][c]) j = f[j];117 j = ch[j][c];118 if(val[j])119 doA(j);120 if(val[last[j]])121 doB(last[j]);122 }123 }124 void getFail() {125 queue<int> q;126 f[0] = 0;127 for(int c = 0; c < SIGMA_SIZE; c++) {128 int u = ch[0][c];129 if(u) {130 f[u] = 0;131 q.push(u);132 last[u] = 0;133 }134 }135 while(!q.empty()) {136 int r = q.front();137 q.pop();138 for(int c = 0; c < SIGMA_SIZE; c++) {139 int u = ch[r][c];140 if(!u) continue;141 q.push(u);142 int v = f[r];143 while(v && !ch[v][c]) v = f[v];144 f[u] = ch[v][c];145 last[u] = val[f[u]] ? f[u] : last[f[u]];146 }147 }148 }149 void delout(char* tmp){150 int u = 0, n = strlen(tmp);151 for(int i = 0; i < n - 1; i++) {152 int c = idx(tmp[i]);153 u = ch[u][c];154 if(val[u])155 vis[val[u]] = false;156 }157 }158 };159 160 AhoCorasickAutomata ac;161 int main() {162 int T; sf("%d", &T);163 REP(cas, T){164 clr(vis, 0);165 ac.init(); int n; sf("%d", &n);166 REP(i, n){167 sf("%s", ctmp);168 deal(st[i], ctmp);169 ac._insert(st[i], i);170 }171 ac.getFail();172 sf("%s", ctmp); deal(text, ctmp);173 ac._find(text); int cnt = 0;174 REP(i, n){175 if(vis[i])176 ac.delout(st[i]);177 }178 REP(i, n){179 if(vis[i]){180 cnt++;181 }182 }183 pf("%d\n", cnt);184 }185 return 0;186 }
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。