[loj6031]字符串

为了方便，用$N=10^{5}$来描述复杂度

（对原串建立SAM）注意到$\sum|w|=qk\le N$，考虑对$q$和$k$的大小关系分类讨论：

1.若$q\le k$，即询问次数较少，将其与原串建立一个广义SAM，然后找到枚举所有区间，倍增找到该区间对应子串的位置，该right集合大小即为答案，时间复杂度为$o(qN\log N)$

（建立广义SAM的实际操作，由于只关心于$s$的子串，并不需要新建节点，会更方便一些）

2.若$k<q$，即串长较短，直接暴力枚举查询串的所有子串，并在原串的SAM上查询其出现次数（即对应节点的right集合大小），然后统计其在$[l_{a},r_{a}],[l_{a+1},r_{a+1}],...,[l_{b},r_{b}]$中出现了几次：

将$m$个区间中相同区间存储位置到同一个vector中，然后即查询该区间对应的vector有几个元素在$[a,b]$中，通过二分即可，时间复杂度为$o(qk^{2}\log N)=o(Nk\log N)$

显然总复杂度为$O(N\sqrt{N}\log N)$，可以通过

 1 #include<bits/stdc++.h>

 2 using namespace std;

 3 #define N 200005

 4 #define ll long long

 5 vector<int>v[N];

 6 int V,n,m,q,l,lst,a,b,nex[N],len[N],R[N],ch[N][26],A[N],B[N],pos[N],Len[N],fa[N][20];

 7 ll ans;

 8 char s[N],ss[N];

 9 void add(int c){

10     int p=lst,np=lst=++V;

11     len[np]=len[p]+1;

12     while ((p)&&(!ch[p][c])){

13         ch[p][c]=np;

14         p=nex[p];

15     }

16     if (!p)nex[np]=1;

17     else{

18         int q=ch[p][c];

19         if (len[q]==len[p]+1)nex[np]=q;

20         else{

21             int nq=++V;

22             nex[nq]=nex[q];

23             nex[q]=nex[np]=nq;

24             len[nq]=len[p]+1;

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

26             while ((p)&&(ch[p][c]==q)){

27                 ch[p][c]=nq;

28                 p=nex[p];

29             }

30         }

31     }

32 }

33 void dfs(int k,int f){

34     fa[k][0]=f;

35     for(int i=1;i<20;i++)fa[k][i]=fa[fa[k][i-1]][i-1];

36     for(int i=0;i<v[k].size();i++){

37         dfs(v[k][i],k);

38         R[k]+=R[v[k][i]];

39     }

40 }

41 int get(int k,int l){

42     for(int i=19;i>=0;i--)

43         if (len[fa[k][i]]>=l)k=fa[k][i];

44     return k;

45 }

46 int main(){

47     scanf("%d%d%d%d%s",&n,&m,&q,&l,s);

48     for(int i=0;i<m;i++)scanf("%d%d",&A[i],&B[i]);

49     V=lst=1;

50     for(int i=0;i<n;i++){

51         add(s[i]-'a');

52         R[lst]=1;

53     }

54     for(int i=2;i<=V;i++)v[nex[i]].push_back(i);

55     dfs(1,0);

56     if (q<=l){

57         for(int ii=1;ii<=q;ii++){

58             scanf("%s%d%d",ss,&a,&b);

59             ans=0;

60             for(int i=0,k=1;i<l;i++){

61                 while ((k>1)&&(!ch[k][ss[i]-'a']))k=nex[k];

62                 Len[i]=len[k];

63                 if (i)Len[i]=min(Len[i],Len[i-1]);

64                 if (ch[k][ss[i]-'a']){

65                     k=ch[k][ss[i]-'a'];

66                     Len[i]++;

67                 }

68                 pos[i]=k;

69             }

70             for(int j=a;j<=b;j++)

71                 if (Len[B[j]]>=B[j]-A[j]+1)ans+=R[get(pos[B[j]],B[j]-A[j]+1)];

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

73         }

74     }

75     else{

76         for(int i=0;i<l*l;i++)v[i].clear();

77         for(int i=0;i<m;i++)v[A[i]*l+B[i]].push_back(i);

78         for(int ii=1;ii<=q;ii++){

79             scanf("%s%d%d",ss,&a,&b);

80             ans=0;

81             for(int i=0;i<l;i++)

82                 for(int j=i,k=1;j<l;j++){

83                     k=ch[k][ss[j]-'a'];

84                     if (!k)break;

85                     int p=i*l+j;

86                     int posl=lower_bound(v[p].begin(),v[p].end(),a)-v[p].begin();

87                     int posr=upper_bound(v[p].begin(),v[p].end(),b)-v[p].begin()-1;

88                     ans+=(ll)R[k]*max(posr-posl+1,0);

89                 }

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

91         }

92     }

93     return 0;

94 }

巴特西

[loj6031]字符串

最新文章

热门文章