# Gym 101741k consistent occurrences

## 根号分治

Posted by yjjr's blog on April 3, 2018

# 题目

Let us define a consistent set of occurrences of string t in string s as a set of occurrences of t in s such that no two occurrences intersect (in other words, no character position in s belongs to two different occurrences).

You are given a string s consisting of n lowercase English letters, and m queries. Each query contains a single string ti.

For each query, print the maximum size of a consistent set of occurrences of t in s.

## Input

The first line contains two space-separated integers n and m: the length of string s and the number of queries (1 ≤ n ≤ $10^5$, 1 ≤ m ≤ $10^5$).

The second line contains the string s consisting of n lowercase English letters.

Each of the next m lines contains a single string ti consisting of lowercase English letters: the i-th query (1 ≤ abs(ti) ≤ n, where abs(ti) is the length of the string ti).

It is guaranteed that the total length of all ti does not exceed 105 characters.

## Output

For each query i, print one integer on a separate line: the maximum size of a consistent set of occurrences of ti in s.

## Example

### Input

6 4
aaaaaa
a
aa
aaa
aaaa


## Output

6
3
2
1


# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define pa pair <int,int>
#define mp make_pair
#define fi first
#define se second
const int maxn=1e5+6;
const int bas[2]={11257,12257};
const int Mod[2]={1e9+7,1e9+9};
int n,m,all,cur,l[maxn],r[maxn],ans[maxn],len[maxn],h[2][maxn],pwd[2][maxn];
map<pa,pa>cnt;
char s[maxn],t[maxn];
inline void solve(int len){
cnt.clear();
rep(i,len,n){
pa val=mp((h[0][i]-1ll*h[0][i-len]*pwd[0][len]%Mod[0]+Mod[0])%Mod[0],(h[1][i]-1ll*h[1][i-len]*pwd[1][len]%Mod[1]+Mod[1])%Mod[1]);
if(cnt.find(val)==cnt.end())cnt[val]=mp(1,i);
else if(i-cnt[val].se<len)continue;else ++cnt[val].fi,cnt[val].se=i;
}
rep(i,1,m)
if(r[i]-l[i]+1==len){
pa cur=mp(0,0);
rep(j,l[i],r[i])cur=mp((1ll*cur.fi*bas[0]+t[j])%Mod[0],(1ll*cur.se*bas[1]+t[j])%Mod[1]);
ans[i]=cnt[cur].fi;
}
}
int main(){
scanf("%s",s+1);
pwd[0][0]=pwd[1][0]=1;
rep(j,0,1)
rep(i,1,n){
h[j][i]=(1ll*h[j][i-1]*bas[j]+s[i])%Mod[j];
pwd[j][i]=1ll*pwd[j][i-1]*bas[j]%Mod[j];
}
rep(i,1,m){
scanf("%s",t+cur+1);
l[i]=cur+1,len[i]=strlen(t+cur+1);
cur+=len[i],r[i]=cur;
}
sort(len+1,len+1+m),all=unique(len+1,len+1+m)-len-1;
rep(i,1,all)solve(len[i]);
rep(i,1,m)printf("%d\n",ans[i]);
return 0;
}