Contest Hunter - IHHH

題意：

給出n個字元串和m個詢問；

每個詢問有l,r和一個字元串；

查詢[l,r]區間中的所有是詢問字元串的子串的最大長度；

n<=100000，m<=100000，字元串總長度<=500000；

此題為CH【弱省胡策】 #1 T2；

題解：

一道好題，感覺正解說起來隻是一句話但是真是很有道理。。

就是說：将詢問拆成log個區間，對線段樹每個結點建AC自動機分别處理；

這樣每個詢問都隻詢問了log個區間，每個字元串也隻被log個結點覆寫；

時間複雜度O(nlogn*26)，代碼極其好寫。。

實際上這樣也就是處理區間問題的基本方法之一，拆分成log個區間來做，用線段樹一樣的分析來保證複雜度；

不要忘了取模哦XD

代碼：

#include<queue>
#include<vector>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 110000
#define LEN 610000
#define S 26
#define lson l,mid,no<<1
#define rson mid+1,r,no<<1|1
#define vec vector<int>
#define iter vec::iterator
using namespace std;
char buf1[LEN];
char* str[N];
char buf2[LEN];
char* p[N];
int L[N],R[N];
int ans[N];
vec query[N<<2];
int next[LEN][S],fail[LEN],len[LEN],tot;
queue<int>q;
int newnode()
{
	int ret=++tot;
	memset(next[ret],0,sizeof(int)*S);
	fail[ret]=len[ret]=0;
	return ret;
}
void init()
{
	tot=0;
	newnode();
}
void Insert(char* s)
{
	int p=1,index,l=0;
	while(*s!='\0')
	{
		index=*s-'a';
		if(!next[p][index])
			next[p][index]=newnode();
		p=next[p][index];
		s++;
		l++;
	}
	len[p]=max(len[p],l);
}
void Build()
{
	int x,i,temp,p;
	q.push(1);
	while(!q.empty())
	{
		x=q.front(),q.pop();
		for(i=0;i<S;i++)
		{
			if(next[x][i])
			{
				p=next[x][i];
				temp=fail[x];
				while(temp&&next[temp][i]==0)
					temp=fail[temp];
				if(temp)
					fail[p]=next[temp][i],len[p]=max(len[fail[p]],len[p]);
				else
					fail[p]=1;
				q.push(p);
			}
			else
			{
				temp=fail[x];
				while(temp&&next[temp][i]==0)
					temp=fail[temp];
				if(temp)
					next[x][i]=next[temp][i];
				else
					next[x][i]=1;
			}
		}
	}
}
int calc(char* s)
{
	int p=1,ret=0;
	while(*s!='\0')
	{
		p=next[p][*s-'a'];
		ret=max(ret,len[p]);
		s++;
	}
	return ret;
}
void update(int l,int r,int no,int st,int en,int val)
{
	if(st<=l&&r<=en)
		query[no].push_back(val);
	else
	{
		int mid=l+r>>1;
		if(en<=mid)		update(lson,st,en,val);
		else if(st>mid)	update(rson,st,en,val);
		else	update(lson,st,en,val),update(rson,st,en,val);
	}
}
void slove(int l,int r,int no)
{
	if(!query[no].empty())
	{
		init();
		for(int i=l;i<=r;i++)
			Insert(str[i]);
		Build();
		for(iter it=query[no].begin();it!=query[no].end();it++)
			ans[*it]=max(calc(p[*it]),ans[*it]);
	}
	if(l==r)	return ;
	int mid=l+r>>1;
	slove(lson);
	slove(rson);
}
int main()
{
	int n,m,i,j,k,x,y;
	scanf("%d%d",&n,&m);
	str[0]=buf1,p[0]=buf2;
	for(i=1;i<=n;i++)
	{
		str[i]=str[i-1]+strlen(str[i-1])+1;
		scanf("%s",str[i]);
	}
	for(i=1;i<=m;i++)
	{
		p[i]=p[i-1]+strlen(p[i-1])+1;
		scanf("%d%d%s",L+i,R+i,p[i]);
		update(1,n,1,L[i],R[i],i);
	}
	slove(1,n,1);
	for(i=1;i<=m;i++)
		printf("%d\n",ans[i]%998244353);//千萬别忘了取模！！！！ 
	return 0;
}