大 LCP 时代(stupid.*)
题目描述
LCP 就是传说中的最长公共前缀，至于为什么要加上一个大字，那是因为…你会知道的（有大病）。
首先，求LCP就要有字符串。既然那么需要它们，那就给出n个字符串好了。
于是你需要回答询问大LCP：询问给出一个 \(k\),你需要求出前 \(k\) 个字符串中两两的 LCP 最大值是多少。
输入描述
第一行一个整数 \(N\)、\(Q\)，分别表示字符串个数和询问次数。
接下来 \(N\) 行，每行一个字符串。
再 \(Q\) 行，每行一个正整数 \(k\)。
输出描述
\(Q\) 行，依次分别表示对 \(Q\) 个询问的答案。
输入输出样例
输入样例#1
3 3
a
b
ab
1
2
3
输出样例#1
0
0
1
提示/说明
数据范围
- 对于 \(30\)% 的数据，字符串的总长度不超过 \(10^4\)，\(1 \leq N \leq 10^3\)，\(1 \leq Q \leq 10\)。
- 另外 \(30\)% 的数据，字符串的总长度不超过 \(10^4\)，\(1 \leq N \leq 10^3\)，\(1 \leq Q \leq 10^3\)。
- 对于 \(100\)% 的数据，字符串的总长度不超过 \(10^6\)，\(1 \leq N \leq 10^5\)，\(1 \leq Q \leq 10^5\)。
解题报告
wow！超级善良的字符串题。
显然，我们不需要执着于在线查询，离线计算每一个 \(k\) 是更好的选择。
在转化一下，我们只需求出插入第 \(k\) 个字符串时，它和前 \(k-1\) 个字符串的最大 LCP 就可以了，设这个值为 \(ans_k\)。我们只需在最后对数组 \(ans\) 求一次前缀最大值，就可以求出前 \(k\) 个字符串的最大 LCP。
那么怎么求 \(ans_k\)。
直接上字典树。
显然，我们知道字典树在存储字符串时会合并相同前缀，这正适合求 \(ans_k\)，我们只需在把字符串 \(k\) 插入字典树时统计以下已存在的节点就好了。
代码如下：
#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1001100;
const int chn=26;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch)) { x=x*10+ch-'0'; ch=getchar(); }return f*x;
}int n,m;
int ans[N];int T[N<<4][chn],idx;
char s[N];inline int Invert(char *s)
{int u=0,ans=0;for(int i=1;s[i];i++){int ch=s[i]-'a';if(!T[u][ch])T[u][ch]=++idx;else ans++;u=T[u][ch];}return ans;
}signed main()
{freopen("stupid.in","r",stdin);freopen("stupid.out","w",stdout);n=read(),m=read();for(int i=1;i<=n;i++){scanf("%s",s+1);s[strlen(s+1)+1]=0;ans[i]=Invert(s);}for(int i=1;i<=n;i++)ckmax(ans[i],ans[i-1]);for(int i=1;i<=m;i++)printf("%d\n",ans[read()]);return 0;
}