广义sam。。
#include #include #include using namespace std;const int MAXN = 1000010;struct SAM{ int ch[26]; int len, fa;}sam[MAXN << 1];int las = 1, cnt = 1, v[MAXN << 1], sz[MAXN << 1];int len[MAXN], tot, n, m;inline void add(int c){ int p = las; int np = las = ++cnt; sam[np].len = sam[p].len + 1; for(; p && !sam[p].ch[c]; p = sam[p].fa) sam[p].ch[c] = np; if(!p) sam[np].fa = 1; else{ int q = sam[p].ch[c]; if(sam[q].len == sam[p].len + 1) sam[np].fa = q; else{ int nq = ++cnt; sam[nq] = sam[q]; sam[nq].len = sam[p].len + 1; sam[q].fa = sam[np].fa = nq; for(; p && sam[p].ch[c] == q; p = sam[p].fa) sam[p].ch[c] = nq; } }}char a[MAXN];void update(int x, int y){ for(; x && v[x] != y; x = sam[x].fa){ v[x] = y; ++sz[x]; }}int ans;int main(){ scanf("%d%d", &n, &m); getchar(); for(int i = 1; i <= n; ++i){ las = 1; char ch; while((ch = getchar()) != '\n') add(a[++tot] = ch - 'a'), ++len[i]; }tot = 0; for(int i = 1; i <= n; ++i) for(int j = 1, x = 1; j <= len[i]; ++j) update(x = sam[x].ch[a[++tot]], i); for(int i = 1; i <= m; ++i){ ans = 0; int p = 1; scanf("%s", a); int len = strlen(a); for(int j = 0; j < len; ++j) if(sam[p].ch[a[j] - 'a']) p = sam[p].ch[a[j] - 'a']; else{ ans = -1; break; } if(ans) ans = 0; else ans = sz[p]; printf("%d\n", ans); } return 0;}