题目链接：https://www.luogu.org/problemnew/show/P3808
学模板可以参考这篇博客：https://blog.csdn.net/weixin_43768644/article/details/98605417
新手の代码：
#include<cstdio> #include<cstring> #include<queue> using namespace std; const int maxnode = 1e6+5; const int sigma_size = 26; int trie[maxnode][sigma_size],sz; int val[maxnode]; int last[maxnode],fail[maxnode]; queue<int>que; char s[maxnode]; void init(int x) { val[x] = 0; memset(trie[x],0,sizeof trie[x]); } int idx(char s){return s-'a';} void insert(char *s) { int u = 0; for (int i=0;s[i];i++){ int v = idx(s[i]); if (!trie[u][v]){ init(sz); trie[u][v] = sz++; } u = trie[u][v]; } val[u]++; } void getfail() { fail[0] = 0; for (int c=0;c<sigma_size;c++) if (trie[0][c]){ int u = trie[0][c]; que.push(u); fail[u] = last[u] = 0; } while (!que.empty()){ int r = que.front(); que.pop(); for (int c=0;c<sigma_size;c++){ int u = trie[r][c]; if (!u){///说的就是这个地方 trie[r][c] = trie[fail[r]][c]; continue; } que.push(u); int v = fail[r]; while (v && !trie[v][c]) v = fail[v]; fail[u] = trie[v][c]; last[u] = val[fail[u]]? fail[u]:last[fail[u]]; } } } int cal(int j) { int ans = 0; while (j){ ans += val[j]; val[j] = 0;///如果是统计匹配串出现模板串总数，而不是几种的话，这行去掉 j = last[j]; } return ans; } int Find(char *s) { int j=0,ans=0; for (int i=0;s[i];i++){ int c = idx(s[i]); j = trie[j][c]; if (val[j]) ans += cal(j); else if (last[j]) ans += cal(last[j]); } return ans; } int main() { int n; sz = 1; scanf("%d",&n); while (n--) scanf("%s",s),insert(s); getfail(); /* for (int i=1;i<sz;i++) printf("fail[%d]=%d last[%d]=%d\n",i,fail[i],i,last[i]); */ scanf("%s",s); printf("%d\n",Find(s)); return 0; }
