ACM-ICPC 2018 焦作赛区网络预赛 H题 String and Times（SAM）

Now you have a string consists of uppercase letters, two integers

Input

Input has multiple test cases.

For each line, there is a string

$10^6∑length(S)≤2×106,$

Output

For each test case, print the number of the wonderful substrings in a line.

样例输入

AAA 2 3
ABAB 2 2

样例输出

2
3

题目来源

ACM-ICPC 2018 焦作赛区网络预赛

题解：SAM模板题

参考代码：

 1 //H  求子串出现次数在k1=<num<=k2;
 2 #include <bits/stdc++.h>
 3 using namespace std;
 4 const int MAXN = 4e5+10;
 5 char ss[200005];
 6 const int LetterSize = 26;
 7 
 8 int tot, last,ch[MAXN][LetterSize],fa[MAXN],len[MAXN];
 9 int sum[MAXN],tp[MAXN],cnt[MAXN]; 
10 
11 void init()
12 {
13     last = tot = 1;
14     len[1] = 0;
15     memset(ch,0,sizeof ch);
16     memset(fa,0,sizeof fa);
17     memset(cnt,0,sizeof cnt);
18 }
19 
20 void add( int x)
21 {
22     int p = last, np = last = ++tot;
23     len[np] = len[p] + 1, cnt[last] = 1;
24     while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];
25     if(p == 0) fa[np] = 1;
26     else
27     {
28         int q = ch[p][x];
29         if( len[q] == len[p] + 1)
30             fa[np] = q;
31         else
32         {
33             int nq = ++tot;
34             memcpy( ch[nq], ch[q], sizeof ch[q]);
35             len[nq] = len[p] + 1, fa[nq] = fa[q], fa[q] = fa[np] = nq;
36             while( p && ch[p][x] == q)  ch[p][x] = nq, p = fa[p];
37         }
38     }
39 }
40 
41 void toposort()
42 {
43     for(int i = 1; i <= len[last]; i++)   sum[i] = 0;
44     for(int i = 1; i <= tot; i++)   sum[len[i]]++;
45     for(int i = 1; i <= len[last]; i++)   sum[i] += sum[i-1];
46     for(int i = 1; i <= tot; i++)   tp[sum[len[i]]--] = i;
47 }
48 
49 
50 int main()
51 {
52 
53     int k1,k2;
54     while(scanf("%s",ss)!=EOF)
55     {
56         init();
57         scanf("%d%d",&k1,&k2);
58         long long ans=0;
59         for(int i=0,len=strlen(ss);i<len;i++) add(ss[i]-'A');
60         toposort();
61         for(int i=tot;i;i--)
62         {
63             int p=tp[i],fp=fa[p];
64             cnt[fp]+=cnt[p];
65             if(cnt[p]>=k1 && cnt[p]<=k2) ans+=len[p]-len[fp];
66         }
67         printf("%lld
",ans);
68     }
69 
70     return 0;
71 }

View Code