meteor多串匹配
Description
Input
第一行为一个整数n，表示文本的长度
第二行为一个长度为n的文本
第三行为一个整数m，表示模式串个数
下接m行，每行一个模式串
Output
共m行，若第i个模式串在文本中出现过则第i行输出YES，否则输出NO
数据范围
对于30%的数据，n<=10^3，m<=10^3；
对于80%的数据，n<=10^5，m<=10^4；
对于100%的数据，n<=10^5，m<=10^5。
输入文件大小不超过1M。
Sample Input
25
saintzeuscynthiathenahere
3
cynthia
hera
athena
Sample Output
YES
NO
YES
Source
后缀数组
给定一个固定待匹配串S，长度为n，然后每次输入一个模式串P，长度为
m，要求返回P 在S 中的一个匹配或者返回匹配失败。所谓匹配指某个位置i
满足1≤i≤n-m+1 使得S[i..(i+m-1)]=P，也即Suffix(i)=mP。
我们知道，如果只有一个模式串，最好的算法就是KMP 算法，时间复杂
度为O(n+m)，但是如果有多个模式串，我们就要考虑做适当的预处理使得对每
个模式串进行匹配所花的时间小一些。
最简单的预处理莫过于建立S 的后缀数组（先在S 的后面添加'$'），然后每
次寻找匹配转化为用二分查找法在SA 中找到和P 的公共前缀最长的一个后缀，
判断这个最长的公共前缀是否等于m。
这样，每次比较P 和一个后缀的复杂度为O(m)，因为最坏情况下可能比较
了m 个字符。二分查找需要调用比较的次数为O(logn)，因此总复杂度为
O(mlogn)，于是每次匹配的复杂度从O(n+m)变为O(mlogn)，可以说改进了不
少。
可是这样仍然不能令我们满足。前面提到LCP 可以增加后缀数组的威力，
我们来试试用在这个问题上。
我们分析原始的二分查找算法，大体有以下几步：
Step 1 令 left=1,right=n,max_match=0。
Step 2 令 mid=(left+right)/2（这里“/”表示取整除法）。
Step 3 顺次比较Suffix(SA[mid])和P 的对应字符，找到两者的最长公共
前缀r，并判断出它们的大小关系。若r>max_match则令max_match=r,ans=mid。
Step 4 若Suffix(SA[mid])<P 则令left=mid+1，若Suffix(SA[mid])>P 则令
right=mid-1，若Suffix(SA[mid])=P 则转至Step 6。
Step 5 若 left<right 则转至Step 2，否则至Step 6。
Step 6 若 max_match=m则输出ans，否则输出“无匹配”。
注意力很快集中在Step 3，如果能够避免每次都从头开始比较Suffix(SA[mid])
和P 的对应字符，也许复杂度就可以进一步降低。
类似于前面求height 数组，我们考虑利用以前求得的最长公共前缀作为比
较的“基础”，避免冗余的字符比较。
在比较Suffix(SA[mid])和P 之前，我们先用常数时间计算LCP(mid,ans)，
然后比较LCP(mid,ans)和max_match：
情况一：LCP(mid,ans)<max_match，则说明Suffix(SA[mid])和P 的最长公
共前缀就是LCP(mid,ans)，即直接可以确定Step 3 中的r=LCP(mid,ans)，所以
可以直接比较两者的第r+1 个字符（结果一定不会是相等）就可以确定
Suffix(SA[mid])和P 的大小。这种情况下，字符比较次数为1 次。
情况二：LCP(mid,ans)≥max_match，则说明Suffix(SA[mid])和Suffix(SA[ans])
的前max_match个字符一定是相同的，于是Suffix(SA[mid])和P 的前max_match
个字符也是相同的，于是比较两者的对应字符可以从第max_match+1 个开始，
最后求出的r 一定大于等于原先的max_match，字符比较的次数为rmax_
match+1，不难看出Step 3 执行过后max_match将等于r。
设每次Step 3 执行之后max_match 值增加的量为Δmax。在情况一中，
Δmax=0，字符比较次数为1=Δmax+1；在情况二中，Δmax=r-max_match，字符
比较次数为r-max_match+1，也是Δmax+1。综上所述，每次Step 3 进行字符比
较的次数为Δmax+1。
总共的字符比较次数为所有的Δmax累加起来再加上Step 3执行的次数。所
有Δmax累加的结果显然就是最后的max_match值，不会超过len(P)=m，而Step
3 执行的次数为O(logn)，因此总共的字符比较次数为O(m+logn)。而整个算法
的复杂度显然和字符比较次数同阶，为O(m+logn)。
至此，问题得到圆满解决，通过O(nlogn)的时间进行预处理（构造后缀数
组、名词数组，计算height 数组，RMQ 预处理），之后就可以在O(m+logn)的
时间内对一个长度为m 的模式串P 进行模式匹配，这仅仅是在读入P 的复杂度
上附加了logn的复杂度，是非常优秀的。
code:
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #define maxn 100010 using namespace std; char ch,s[maxn],ss[maxn]; int n,m,l,r,mid,len,tot,max_match,t_len,ans; int SA[maxn],rank[maxn<<1],tmp[maxn],sum[maxn],height[maxn],tree[maxn<<2]; bool bo,stop; void read(int &x){ for (ch=getchar();!isdigit(ch);ch=getchar()); for (x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar()); } void get_SA(){ int *x=t1,*y=t2; for (int i=1;i<=n;i++) sum[x[i]=s[i]]++; for (int i=1;i<=255;i++) sum[i]+=sum[i-1]; for (int i=1;i<=n;i++) SA[sum[x[i]]--]=i; tot=0; for (int len=1;tot<n;len<<=1,m=tot){ tot=0; for (int i=n-len+1;i<=n;i++) y[++tot]=i; for (int i=1;i<=n;i++) if (SA[i]>len) y[++tot]=SA[i]-len; memset(sum,0,sizeof(sum)); for (int i=1;i<=n;i++) sum[x[y[i]]]++; for (int i=1;i<=m;i++) sum[i]+=sum[i-1]; for (int i=n;i>=1;i--) SA[sum[x[y[i]]]--]=y[i]; swap(x,y); x[SA[1]]=tot=1; for (int i=2;i<=n;i++){ if (y[SA[i]]!=y[SA[i-1]]||y[SA[i]+len]!=y[SA[i-1]+len]) tot++; x[SA[i]]=tot; } } for (int i=1;i<=n;i++) rank[i]=x[i]; } void get_height(){ for (int i=1,j=0;i<=n;i++){ if (rank[i]==1) continue; while (s[i+j]==s[SA[rank[i]-1]+j]) j++; height[rank[i]]=j; if (j>0) j--; } } inline void build(int k,int l,int r){ if (l==r){ tree[k]=height[l]; return; } int m=(l+r)>>1; build(k<<1,l,m),build((k<<1)+1,m+1,r); tree[k]=min(tree[k<<1],tree[(k<<1)+1]); } inline int answer(int k,int l,int r,int x,int y){ if (l==x&&r==y) return tree[k]; int m=(l+r)>>1; if (y<=m) return answer(k<<1,l,m,x,y); else if (x<=m) return min(answer(k<<1,l,m,x,m),answer((k<<1)+1,m+1,r,m+1,y)); else return answer((k<<1)+1,m+1,r,x,y); } inline int LCP(int i,int j){ if (i==j) return n-SA[i]+1; if (i>j) swap(i,j); return answer(1,1,n,i+1,j); } int main(){ read(n); scanf("%s",s+1); get_SA(),get_height(),build(1,1,n); read(m); for (int i=1;i<=m;i++){ scanf("%s",ss+1); len=strlen(ss+1); l=1,r=n,max_match=ans=0; while (l<=r){ mid=(l+r)>>1,bo=0,stop=0; if (!ans){ int i; for (i=SA[mid];i<=n&&ss[max_match+1]==s[i];i++,max_match++,ans=mid); if (s[i]<ss[max_match+1]) bo=1; } else{ t_len=LCP(ans,mid); if (t_len<max_match){ if (s[t_len+SA[mid]]<ss[t_len+1]) bo=1; } else{ int i; for (i=SA[mid]+max_match;i<=n&&ss[max_match+1]==s[i];i++,max_match++,ans=mid); if (s[i]<ss[max_match+1]) bo=1; } } if (max_match>=len) break; if (bo) l=mid+1; else r=mid-1; } if (max_match>=len) puts("YES"); else puts("NO"); } return 0; }