Singing Superstar HDU - 7064

題意：

問在串T中出現(xiàn)了幾次不相交的串S？
每次有n個串S詢問

題解：

AC自動機(jī)板子題。。
直接上模板

代碼：

#include <bits/stdc++.h> #include <unordered_map> #define debug(a, b) printf("%s = %d\n", a, b); using namespace std; const int maxnode= 5e5; const int sigma_size= 26; int ans= 0; template <typename T> inline void read(T& x) {T f= 1;x= 0;char ch= getchar();while (0 == isdigit(ch)) {if (ch == '-')f= -1;ch= getchar();}while (0 != isdigit(ch))x= (x << 1) + (x << 3) + ch - '0', ch= getchar();x*= f; } template <typename T> inline void write(T x) {if (x < 0) {x= ~(x - 1);putchar('-');}if (x > 9)write(x / 10);putchar(x % 10 + '0'); } struct AC_Automata {int ch[maxnode][sigma_size];int val[maxnode]; // 以單詞結(jié)尾的個數(shù)int f[maxnode]; // fail函數(shù)int last[maxnode]; // last[i]=j表j節(jié)點表示的單詞是i節(jié)點單詞的后綴，且j節(jié)點是單詞節(jié)點int sz;int cnt[maxnode]; //非單詞節(jié)點vis=0,單詞節(jié)點vis=1.如果用find找到了單詞i節(jié)點,那么vis=0.int pos[maxnode], len[maxnode];void init(){sz= 1;memset(ch[0], 0, sizeof(ch[0]));val[0]= 0;last[0]= f[0]= 0;memset(cnt, 0, sizeof(cnt));memset(pos, 0, sizeof(pos));memset(len, 0, sizeof(len));}void insert(char* s){int n= strlen(s), u= 0;for (int i= 0; i < n; i++) {int id= s[i] - 'a';if (ch[u][id] == 0) {ch[u][id]= sz;memset(ch[sz], 0, sizeof(ch[sz]));val[sz++]= 0;}u= ch[u][id];}val[u]= 1;len[u]= n;}void getFail(){queue<int> q;last[0]= f[0]= 0;for (int i= 0; i < sigma_size; i++) {int u= ch[0][i];if (u) {f[u]= last[u]= 0;q.push(u);}}while (!q.empty()) {int r= q.front();q.pop();for (int i= 0; i < sigma_size; i++) {int u= ch[r][i];if (u == 0)continue;q.push(u);int v= f[r];while (v && ch[v][i] == 0)v= f[v];f[u]= ch[v][i];last[u]= val[f[u]] ? f[u] : last[f[u]];}}}void print(int i, int pos1){if (val[i]) {if (pos[i] + len[i] <= pos1) {pos[i]= pos1;cnt[i]++;}print(last[i], pos1);}}void find(char* s){int n= strlen(s), j= 0;for (int i= 0; i < n; i++) {int id= s[i] - 'a';while (j && ch[j][id] == 0)j= f[j];j= ch[j][id];if (val[j])print(j, i + 1);else if (last[j])print(last[j], i + 1);}}int find_T(char* s){int n= strlen(s), u= 0;for (int i= 0; i < n; i++) {int id= s[i] - 'a';u= ch[u][id];}return cnt[u];} }; AC_Automata ac;char word[100080][50]; char s[100005]; int main() {int n;int T;int cas= 0;read(T);while (T--) {scanf("%s", &s);scanf("%d", &n);ac.init();for (int i= 1; i <= n; i++) {scanf("%s", word[i]);ac.insert(word[i]);}ac.getFail();ac.find(s);for (int i= 1; i <= n; i++) {printf("%d\n", ac.find_T(word[i]));}} }

總結(jié)

以上是生活随笔為你收集整理的Singing Superstar HDU - 7064的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。