ACM-ICPC 2018 Jiaozuo Cyber ​​Preliminaries H String and Times (Suffix Array + Tolerance)

Now you have a string consists of uppercase letters, two integers A and B. We call a substring wonderful substring when the times it appears in that string is between A and B (A≤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 S, two integers A and B.

∑length(S)≤2×106,

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

后缀数组求出现K次不同字串的板子题,只需稍作修改,在容斥的时候,减去大于B次的就可以。
代码实现:

/*
Look at the star
Look at the shine for U
*/
#include<bits/stdc++.h>
#define ll long long
#define PII pair<int,int>
#define sl(x) scanf("%lld",&x)
Using namespace std;
Const int N = 200000+10;
Int temp1[N], temp2[N], sam[N], c[N], lcp[N], num[N], Rank[N], len;
Char s[N];
Int dp[N][30];
 
Void RMQ(int* arr, int n)
{
    For(int i = 0; i < n; ++i) dp[i][0] = arr[i];
    For(int j = 1;(1<<j) <= n;++j)
    For(int i = 0;i+(1<<j)-1<n;++i)
    Dp[i][j] = min(dp[i][j-1], dp[i+(1<<(j-1))][j-1]);
}
 
Ll ask(int l,int r)
{
    Int k = 0;
    While((1<<(k+1))<=r-l+1) ++k;
    Ll ans = min(dp[l][k],dp[r-(1<<k)+1][k]);
    Return ans;
}

Bool judge(int* arr, int x, int y, int l)
{
    If(arr[x] == arr[y] && arr[x+l] == arr[y+l]) return true;
    Else return false;
}

Ll query(int l, int r)
{
    If (l == r) return len-sam[r];
    Return ask(l+1,r);
}

Void init(int n, int m)
{
    ++n;
    Int i,j,p,*x = temp1,*y = temp2;
    For(i = 0; i < m; ++i) c[i] = 0;
    For(i = 0; i < n; ++i) c[x[i] = num[i]]++;
    For(i = 1; i < m; ++i) c[i] += c[i-1];
    For(i = n-1;i;--i) sam[--c[x[i]]] = i;
    For(j = 1;j <= n;j <<= 1)
{
        p = 0;
        For(i = n-j; i<n;++i) y[p++] = i;
        For(i = 0;i < n;++i)
If(sam[i] >= j)
y[p++] = sam[i] - j;
        For(i = 0; i < m; ++i) c[i] = 0;
        For(i = 0; i < n; ++i) c[x[y[i]]]++;
        For(i = 1; i < m;++i) c[i] += c[i-1];
        For(i = n-1;i;--i)
Sam[--c[x[y[i]]]] = y[i];
        Swap(x,y);
        p = 1;
x[sam[0]] = 0;
        For (i = 1;i < n;++i)
{
If(judge(y,sam[i-1],sam[i],j)) x[sam[i]] = p-1;
Else x[sam[i]] = p++;
}
        If(p >= n) break;
        m = p;
    }
    Int k = 0;
    N--;
    For(i = 0;i <= n;++i) Rank[sam[i]] = i;
    For(i = 0;i < n;++i)
{
        If(k)--k;
        j = sam[Rank[i]-1];
        While(num[i+k] == num[j+k]) ++k;
        Lcp[Rank[i]] = k;
    }
}

Int main()
{
    Int t,k,x,i,j;
    While(~scanf("%s%d%d",s,&k,&x))
{
        Len = strlen(s);
        For(i = 0;i <= len;i++)
        {
        Rank[i] = lcp[i] = sam[i] = 0;
}
        For (i = 0; i < len; ++i) num[i] = s[i]-'A'+1;
        Num[len] = 0;
        Init(len,30);
        RMQ(lcp,len+1);
        Ll ans = 0;
        For (i = 1;i+k-1 <= len;i++)
{
            Ans += query(i,i+k-1); //at least k
            If(i-1 > 0) ans -= query(i-1,i+k-1);
            If(i+x <= len) ans -= query(i,i+x);
            If(i-1 > 0 && i+x <= len) ans += query(i-1,i+x);
        }
        Printf("%lld\n",ans);
    }
    Return 0;
}