//倍增算法构造后缀数组
//时间复杂度O(nlogn) 空间复杂度O(n)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 110000
int n; //n为处理字符串s的长度
char s[MAXN],tmp[MAXN]; //s为输入的字符串
int sa[MAXN],t[MAXN],t2[MAXN],c[MAXN];
int idx(char c)
{
return c-'a';
}
void print(int *num,int d)
{
printf("\n");
for(int i=0;i<d;i++)
printf("%d %d\n",i,num[i]);
printf("\n");
}
//构造字符串s的后缀数组,每个字符值必须为0--m-1
void build_sa(int m)
{
int i,*x=t,*y=t2;
//基数排序
for(i=0;i<m;i++) c[i]=0;
for(i=0;i<n;i++) c[x[i]=idx(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(int k=1;k<=n;k<<=1)
{
int p=0;
//直接利用sa数组排序第二关键字
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;
for(i=0;i<n;i++) c[x[y[i]]]++;
for(i=0;i<m;i++) c[i]+=c[i-1];
for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
//根据sa和y数组计算新的x数组
swap(x,y);
p=1;x[sa[0]]=0;
for(i=1;i<n;i++)
x[sa[i]]=y[sa[i-1]]==y[sa[i]] && y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n)
break; //以后即使继续倍增,sa也不会改变,退出
m=p; //下次基数排序的最大值
}
}
int m; //模版长度
int cmp_suffix(char *pattern,int p) //判断模版s是否为后缀p的前缀
{
return strncmp(pattern,s+sa[p],m);
}
//多模版匹配问题。直接在后缀数组里进行二分查找,找到其中一个匹配位置(可以改成找出所有位置的代码)
//每次查询的时间复杂度为O(mlogn),其中n为文本串的长度,m为模式串的长度
/*
int find(char *p)
{
m=strlen(p);
if(cmp_suffix(p,0)<0) return -1;
if(cmp_suffix(p,n-1)>0) return -1;
int L=0,R=n-1;
while(L<=R) //二分查找
{
int M=L+(R-L)/2;
int res=cmp_suffix(p,M);
if(!res)
return M;
if(res<0)
R=M-1;
else
L=M+1;
}
return -1; //找不到
}
*/
//输出所有位置的find函数
int find(char *p)
{
m=strlen(p);
if(cmp_suffix(p,0)<0) return -1;
if(cmp_suffix(p,n-1)>0) return -1;
int L=0,R=n-1;
while(L<=R) //二分查找
{
int M=L+(R-L)/2;
int res=cmp_suffix(p,M);
if(!res)
{
printf("%d\n",sa[M]);
for(int i=M-1;i>=0;i--)
if(cmp_suffix(p,i)==0)
{
printf("%d\n",sa[i]);
}
else
break;
for(int i=M+1;i<n;i++)
if(cmp_suffix(p,i)==0)
{
printf("%d\n",sa[i]);
}
else
break;
return M;
}
if(res<0)
R=M-1;
else
L=M+1;
}
return -1; //找不到
}
int main()
{
int i,t,x;
freopen("e:\\in.txt","r",stdin);
while(scanf("%s",s)==1)
{
n=strlen(s);
build_sa(26);
printf("\nsa:"); print(sa,n);
scanf("%d",&t);
for(i=1;i<=t;i++)
{
scanf("%s",tmp);
x=find(tmp);
if(x==-1)
printf("%d\n",x);
}
}
return 0;
}