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

Now you have a string consists of uppercase letters, two integers AA and BB. We call a substring wonderful substring when the times it appears in that string is between AA and BB (A \le times \le BA≤times≤B). Can you calculate the number of wonderful substrings in that string?

Input

Input has multiple test cases.

For each line, there is a string SS, two integers AA and BB.

\sum length(S) \le 2 \times 10^6∑length(S)≤2×106,

1 \le A \le B \le length(S)1≤A≤B≤length(S)

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模板题

参考代码：

 //H  求子串出现次数在k1=<num<=k2;

 #include <bits/stdc++.h>

 using namespace std;

 const int MAXN = 4e5+;

 char ss[];

 const int LetterSize = ;

 int tot, last,ch[MAXN][LetterSize],fa[MAXN],len[MAXN];

 int sum[MAXN],tp[MAXN],cnt[MAXN]; 

 void init()

 {

     last = tot = ;

     len[] = ;

     memset(ch,,sizeof ch);

     memset(fa,,sizeof fa);

     memset(cnt,,sizeof cnt);

 }

 void add( int x)

 {

     int p = last, np = last = ++tot;

     len[np] = len[p] + , cnt[last] = ;

     while( p && !ch[p][x]) ch[p][x] = np, p = fa[p];

     if(p == ) fa[np] = ;

     else

     {

         int q = ch[p][x];

         if( len[q] == len[p] + )

             fa[np] = q;

         else

         {

             int nq = ++tot;

             memcpy( ch[nq], ch[q], sizeof ch[q]);

             len[nq] = len[p] + , fa[nq] = fa[q], fa[q] = fa[np] = nq;

             while( p && ch[p][x] == q)  ch[p][x] = nq, p = fa[p];

         }

     }

 }

 void toposort()

 {

     for(int i = ; i <= len[last]; i++)   sum[i] = ;

     for(int i = ; i <= tot; i++)   sum[len[i]]++;

     for(int i = ; i <= len[last]; i++)   sum[i] += sum[i-];

     for(int i = ; i <= tot; i++)   tp[sum[len[i]]--] = i;

 }

 int main()

 {

     int k1,k2;

     while(scanf("%s",ss)!=EOF)

     {

         init();

         scanf("%d%d",&k1,&k2);

         long long ans=;

         for(int i=,len=strlen(ss);i<len;i++) add(ss[i]-'A');

         toposort();

         for(int i=tot;i;i--)

         {

             int p=tp[i],fp=fa[p];

             cnt[fp]+=cnt[p];

             if(cnt[p]>=k1 && cnt[p]<=k2) ans+=len[p]-len[fp];

         }

         printf("%lld\n",ans);

     }

     return ;

 }

巴特西