Lang:G++
Edit12345678910111213141516171819202122232425262728293031#include <cstdio>#include <cstring>#include <algorithm>#include <iostream>using namespace std;const int maxn = 200000 + 5;char s[maxn];char str[maxn];int sa[maxn];int t[maxn];int t2[maxn];int c[maxn];int n;void build_sa(int m,int n){int *x=t,*y=t2,k,i;for(i=0;i<m;i++)c[i]=0;for(i=0;i<n;i++)c[x[i]=s[i]]++;for(i=1;i<m;i++)c[i]+=c[i-1];for(i=n-1;i>=0;i--)sa[--c[x[i]]]=i;for(k=1;k<=n;k<<=1){int p=0;for(i=n-k;i<n;i++)y[p++]=i;for(i=0;i<n;i++)if(sa[i]>=k)y[p++]=sa[i]-k;for(i=0;i<m;i++)c[i]=0;