题目链接：here
题解：首先找最短的串，长度为minlen， 可知长度更长的串答案一定为0， 而长度等于minlen的串答案相等。
其实稍微想一下就知道了，比赛的时候上来就把KMP否了，一直在想别的做法。。。一点也不知道思考啊。。。
1 #include <bits/stdc++.h> 2 using namespace std; 3 #define LL long long 4 const int maxn = 1e6 + 10; 5 const int mod = 998244353; 6 char s[maxn * 3]; 7 int l[maxn]; 8 int nxt[maxn * 2]; 9 10 void getfail(char *p){ 11 int len = strlen(p); 12 nxt[0] = nxt[1] = 0; 13 for(int i = 1; i < len; i++){ 14 int j = nxt[i]; 15 while(j && p[i] != p[j]) j = nxt[j]; 16 nxt[i + 1] = p[i] == p[j] ? j + 1 : 0; 17 } 18 } 19 20 LL kmp(char *s, char *p){ 21 int lens = strlen(s), lenp = strlen(p); 22 int cnt = 0; 23 int j = 0; 24 for(int i = 0; i < lens; i++){ 25 while(j && s[i] != p[j]) j = nxt[j]; 26 if(s[i] == p[j]) j++; 27 if(j == lenp){ 28 j = nxt[j]; 29 cnt++; 30 } 31 } 32 return cnt; 33 } 34 35 int main(){ 36 int n; 37 scanf("%d", &n); 38 int minid = n, minlen = maxn * 3; 39 int pos = 0; 40 for(int i = 0; i < n; i++){ 41 scanf("%s", s + pos); 42 l[i] = pos; 43 int len = strlen(&s[pos]); 44 if(minlen > len) minid = i, minlen = len; 45 pos = pos + len + 1; 46 } 47 LL ans = 1; 48 char *p = &s[l[minid]]; 49 getfail(p); 50 for(int i = 0; i < n; i++) if(i != minid){ 51 ans = ans * kmp(&s[l[i]], p) % mod; 52 } 53 for(int i = 0; i < n; i++) { 54 if(strlen(&s[l[i]]) == minlen) printf("%lld ", ans); 55 else puts("0"); 56 } 57 58 }