ACM-ICPC 2018 焦作赛区网络预赛 H. String and Times—— 后缀自动机

本文主要是介绍ACM-ICPC 2018 焦作赛区网络预赛 H. String and Times—— 后缀自动机，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Now you have a string consists of uppercase letters, two integers
AA
A and
BB
B. We call a substring wonderful substring when the times it appears in that string is between
AA
A and
BB
B (
A≤times≤BA \le times \le 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
SS
S, two integers
AA
A and
BB
B.
∑length(S)≤2×106\sum length(S) \le 2 \times 10^6
∑length(S)≤2×10
6
,
1≤A≤B≤length(S)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

题意：

给你一个串，x,y，叫你求出现次数在x,y之间的不同子串个数

题解：

后缀数组我并不会求至少出现k次的子串QAQ，看别人的题解发现原来是后缀自动机的模板题。。。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e5+1000;
char s[maxn];
int len,k,n,m;
char temp[5];
struct SAM{int last,cnt,nxt[maxn*2][26],fa[maxn*2],l[maxn*2],num[maxn*2];int ans;void init(){last = cnt=1;memset(nxt[1],0,sizeof nxt[1]);fa[1]=l[1]=num[1]=0;ans=0;}int inline newnode(){cnt++;memset(nxt[cnt],0,sizeof nxt[cnt]);fa[cnt]=l[cnt]=num[cnt]=0;return cnt;}void add(int c){int p = last;int np = newnode();last = np;l[np] =l[p]+1;while (p&&!nxt[p][c]){nxt[p][c] = np;p = fa[p];}if (!p){fa[np] =1;}else{int q = nxt[p][c];if (l[q]==l[p]+1){fa[np] =q;}else{int nq = newnode();memcpy(nxt[nq],nxt[q],sizeof nxt[q]);fa[nq] =fa[q];num[nq] = num[q];l[nq] = l[p]+1;fa[np] =fa[q] =nq;while (nxt[p][c]==q){nxt[p][c]=nq;p = fa[p];}}}int temp = last;while (temp){if (num[temp]>=k){break;}num[temp]++;if (num[temp]==k){ans+=l[temp]-l[fa[temp]];}temp = fa[temp];}}
}sam;
int main(){while(~scanf("%s",s)){len = strlen(s);sam.init();scanf("%d%d",&k,&m);for (int i=0;i<len;i++){sam.add(s[i]-'A');}int ans=sam.ans;k=m+1;sam.init();for (int i=0;i<len;i++){sam.add(s[i]-'A');}printf("%d\n",ans-sam.ans);}return 0;
}

这篇关于ACM-ICPC 2018 焦作赛区网络预赛 H. String and Times—— 后缀自动机的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---