链接：http://acm.hdu.edu.cn/showproblem.php?pid=5069

题意：给出n个串，m个询问，每个询问(u,v)，求u的一个最长后缀是v的前缀。

思路：离线。将关于u的后缀的查询放在一起，然后将u插入后缀自动机。对于每个v跑一遍即可。

struct SAM{    SAM *son[4],*pre;    int len;	int ok;	void init()	{		clr(son,0);		pre=0;		ok=0;	}};SAM sam[N],*head,*last;int cnt;void initSam(){    head=last=&sam[0];	head->init();    cnt=1;}int get(char x){	if(x=='A') return 0;	if(x=='T') return 1;	if(x=='G') return 2;	return 3;}void insert(int x){    SAM *p=&sam[cnt++],*u=last;	p->init();    p->len=last->len+1;    last=p;    for(;u&&!u->son[x];u=u->pre) u->son[x]=p;    if(!u) p->pre=head;    else if(u->son[x]->len==u->len+1) p->pre=u->son[x];    else    {        SAM *r=&sam[cnt++],*q=u->son[x];        *r=*q; r->len=u->len+1;        p->pre=q->pre=r;        for(;u&&u->son[x]==q;u=u->pre) u->son[x]=r;    }}char s[N*2];int cur;int start[N],len[N];vector
     
      
        > V[N];int ans[N];map
       
         mp;int n,m;int main(){//	FFF;	while(scanf("%d%d",&n,&m)!=-1)	{		cur=0;		int i;		for(i=1;i<=n;i++)		{			scanf("%s",s+cur);			start[i]=cur;			len[i]=strlen(s+cur);			cur+=len[i]+3;		}		for(i=1;i<=m;i++)		{			int u,v;			scanf("%d%d",&u,&v);			V[u].pb(MP(v,i));		}				for(i=1;i<=n;i++) if(SZ(V[i])>0)		{			int j;			initSam();			for(j=start[i];s[j];j++)  insert(get(s[j]));			SAM *p=last;			while(p!=NULL) p->ok=1,p=p->pre;			mp.clear();			for(j=0;j
        
         son[x])					{						cur++;						p=p->son[x];						if(p->ok) tmp=max(tmp,cur);					}					else break;				}				mp[k]=tmp;				ans[id]=tmp;			}			V[i].clear();		}		for(i=1;i<=m;i++) printf("%d\n",ans[i]);	}}