【Wannafly挑战赛9-B】数一数

链接：https://www.nowcoder.net/acm/contest/71/B

题目就不贴了。。

设res[i]为第i行的最终结果，可以想到，res[i]为0或不为0。长度不是最短的字符串res一定0，因为res是所有子串数量的乘积，对于每个字符串，只有长度最短的字符串乘过之后才会有结果，其余的res都是0。有多个长度最短的，结果都一样，总之...看代码就懂了（逃。之后就是KMp了（好长时间没复习kmp都忘了惹Σ(ﾟдﾟ;)

上代码：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long LL;
 4 const int mod = 998244353;
 5 const int N = 1e6+3;
 6 string s[N];
 7 char s1[N*2];
 8 int id[N], Next[N*2];
 9 LL res[N];
10 void make(string s, int m)
11 {
12     int i, j;
13     for(i=1, j=0; i<m; i++)
14     {
15         while(j > 0 && s[i] != s[j])
16             j = Next[j-1];
17         if(s[i] == s[j])
18             j++;
19         Next[i] = j;
20     }
21 }
22 int kmp(string s1, string s2)
23 {
24     int i, j, num = 0;
25     int l1 = s1.size();
26     int l2 = s2.size();
27     Next[0] = 0;
28     make(s1, l1);
29     for(i = 0, j = 0; i < l2; i++)
30     {
31         while(j > 0 && s1[j] != s2[i])
32             j = Next[j-1];
33         if(s1[j] == s2[i])
34             j++;
35         if(j == l1)
36         {
37             num++;
38             j = Next[j-1];
39         }
40     }
41     return num;
42 }
43 int main()
44 {
45     int n, i, j;
46     cin>>n;
47     for(i = 1; i <= n; i++)
48     {
49         scanf("%s", s1);
50         s[i] = s1;
51         id[i] = i;//用id标号来给长度从小到大排序
52     }
53     sort(id+1, id+1+n, [](int x, int y){return s[x]. size()<s[y].size();});//又学会一种偷懒+的写法(°∀°)ﾉ
54     int m = s[id[1]].size();
55     res[id[1]] = 1;
56     for(j = 2; j <= n; j++)
57         res[id[1]] = (res[id[1]]*kmp(s[id[1]], s[j])%mod)%mod;
58     for(i = 2; i <= n; i++)
59     {
60         if(s[id[i]].size() != m) break;
61         if(s[id[i]].size() == m) res[id[i]] = res[id[1]];
62     }
63     for(i = 1; i <= n; i++)
64         printf("%lld
", res[i]);
65     return 0;
66 }

View Code