 #include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
#define maxn 1000000+5
#define min(a,b) ((a)<(b)?(a):(b))
char s[maxn];
int sa[maxn],h[maxn],height[maxn],rank[maxn];
int k,n;
bool cmp1(const int & a,const int & b)
   {
 return (s[a]<s[b]);
 }
bool cmp2(const int & a,const int & b)
{
return (rank[a]<rank[b] || (rank[a]==rank[b]&&
(a+k<n?rank[a+k]:-1)<(b+k<n?rank[b+k]:-1)));
}
void suffixArray()
{
int i,j;
for(i=0;i<n;i++)
sa[i]=i;
sort(sa,sa+n,cmp1);
for(i=0;i<n;i++)
  {
if(i==0||s[sa[i]]!=s[sa[i-1]])
rank[sa[i]]=i;
else rank[sa[i]]=rank[sa[i-1]];
 }
for(k=1;k<n;k*=2)
{
sort(sa,sa+n,cmp2);
for(i=0;i<n;i++)
{
if( i==0 || (cmp2(sa[i],sa[i-1])||cmp2(sa[i-1],sa[i])) )
h[sa[i]]=i;
else h[sa[i]]=h[sa[i-1]];
}
memcpy(rank, h, n * sizeof(int));
}
height[0] = 0;
for(i = 0, j = 0; i < n; i++)
{
if(rank[i]>0)
{
while(s[sa[rank[i] - 1] + j] == s[i + j])
j++;
height[rank[i]] = j;
if(j > 0) j--;
}
}
}
void rmq_init()
{
int p=rank[0];
int i,smin;
h[0]=n;
smin=INT_MAX;
for(i=p;i>0;i--)
{
if(height[i]<smin)
smin=height[i];
h[sa[i-1]]=smin; //这里放到数组h里面只是复用，以节省空间
}
smin=INT_MAX;
for(i=p+1;i<n;i++)
{
if(height[i]<smin)
smin=height[i];
h[sa[i]]=smin;
}
}
int main()
{
int t,p,x;
scanf("%d", &t);
while(t--)
{
scanf("%s",s);
strrev(s);
n = strlen(s);
s[n]='$';
suffixArray();
rmq_init();
scanf("%d",&p);
while(p--)
{
scanf("%d",&x);
printf("%d\n",h[n-x]);
}
}
return 0;
}
|