You are viewing a single comment's thread. Return to all comments →
C++ -
#include <bits/stdc++.h> #define mo(x) ((x)<P?(x):(x)-P) using namespace std; const int N=100009; const int C=10; const long long P=pow(10,9)+97; int n,m; char c[N*2]; int a[N][C],v[N],v2[N]; long long b[N][C],p[N]; void input(){ scanf("%d%d",&n,&m); assert(1<=min(n,m)&& max(n,m)<=50000); scanf("%s",c+1); } int getmax(int x,int y){ if (x>y) swap(x,y); int r=n-y+1; int l=0,mi,h=0; while (l<r){ mi=(l+r+1)/2; h=0; for (int i=0;h==i && i<C;i++) h+=(((b[x+mi-1][a[x][i]] -b[x -1][a[x][i]])*p[y-x] -b[y+mi-1][a[y][i]] +b[y -1][a[y][i]])%P==0); if (h==C) l=mi; else r=mi-1; } return l; } bool sufcomp(int x,int y){ int d=getmax(x,y); if (d==n-max(x,y)+1) return x>y; int _A=0,_B=0; for (int i=0;i<C;i++){ if (c[x+d]==a[x][i]) _A=i; if (c[y+d]==a[y][i]) _B=i; } return _A<_B; } void pre(){ p[0]=1; for (int i=1;i<N;i++) p[i]=p[i-1]*5021%P; for (int i=1;i<=n;i++) c[i]-='a'; for (int i=0;i<C;i++) a[n+1][i]=i; for (int i=n;i>0;i--){ int I=0; for (int j=0;j<C;j++){ a[i][j]=a[i+1][j]; if (a[i][j]==c[i]) I=j; } while (I--) swap(a[i][I],a[i][I+1]); } for (int i=1;i<=n;i++){ b[i][c[i]]=p[i]; for (int j=0;j<C;j++) b[i][j]=mo(b[i][j]+b[i-1][j]); } for (int i=1;i<=n;i++) v[i]=i; stable_sort(v+1,v+n+1,sufcomp); for (int i=1;i<=n;i++) v2[v[i]]=i; } void sol(){ pre(); while (m--){ int l,r,mi; scanf("%d%d",&l,&r); int x=v2[l]; int d=r-l+1; l=1; r=x; while (l<r){ mi=(l+r)/2; if (getmax(v[x],v[mi])<d) l=mi+1; else r=mi; } int L=l; l=x; r=n; while (l<r){ mi=(l+r+1)/2; if (getmax(v[x],v[mi])<d) r=mi-1; else l=mi; } int R=l; printf("%d\n",R-L+1); } } int main() { input(); sol(); return 0; }
Seems like cookies are disabled on this browser, please enable them to open this website
Similar Strings
You are viewing a single comment's thread. Return to all comments →
C++ -