思路
这道题我用的是AC自动机的做法。
先把子串挂到trie树上，在单词结尾打标记的时候，标记的是当前单词的长度。然后去上面查询母串的时候，每查询到一个单词，就建立一条线段，这条线段的结尾位置是母串当前的位置，开始位置就是用当前位置减去这个单词的长度。
然后只要去判断，选出一些线段，使得这些线段紧挨着(既不相互覆盖，中间也不遗漏)从母串开始位置铺，能铺到的最远的地方。所以只需要一遍bfs就行了。
代码
/*
* @Author: wxyww
* @Date: 2018-12-17 08:38:38
* @Last Modified time: 2018-12-17 09:09:28
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<bitset>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N = 2000000 + 100;
ll read() {
ll x=0,f=1;char c=getchar();
while(c<'0'||c>'9') {
if(c=='-') f=-1;
c=getchar();
}
while(c>='0'&&c<='9') {
x=x*10+c-'0';
c=getchar();
}
return x*f;
}
int trie[1000][30],end[1000];
char s[30];
int tot;
void insert() {
int len = strlen(s + 1);
int now = 0;
for(int i = 1;i <= len;++i) {
int k = s[i] - 'a';
if(!trie[now][k]) trie[now][k] = ++tot;
now = trie[now][k];
}
end[now] = len;
}
struct node {
int l,r;
}e[N];
int ejs;
int fail[N];
char S[N];
queue<int>q;
void build() {
for(int i = 0;i < 26;++i) if(trie[0][i]) q.push(trie[0][i]);
while(!q.empty()) {
int u = q.front();q.pop();
for(int i = 0;i < 26;++i) {
if(trie[u][i]) fail[trie[u][i]] = trie[fail[u]][i],q.push(trie[u][i]);
else trie[u][i] = trie[fail[u]][i];
}
}
}
vector<int>v[N];
void work() {
int len = strlen(S + 1);
ejs = 0;int now = 0;
for(int i = 1;i <= len;++i) {
now = trie[now][S[i] - 'a'];
for(int j = now;j;j = fail[j]) {
if(end[j]) e[++ejs].l = i - end[j] + 1,e[ejs].r = i;
}
}
}
int vis[N];
void bfs() {
q.push(1);
int ans = 0;
for(int i = 1;i <= ejs;++i) v[e[i].l].push_back(i);
memset(vis,0,sizeof(vis));
while(!q.empty()) {
int l = q.front();q.pop();
int k = v[l].size();
for(int i = 0;i < k;++i) {
int z = v[l][i];
if(vis[z]) continue;
vis[z] = 1;
q.push(e[z].r + 1);
ans = max(ans,e[z].r);
}
}
printf("%d
",ans);
int len = strlen(S + 1);
for(int i = 1;i <= len;++i) v[i].clear();
}
int main() {
int n = read(),m = read();
for(int i = 1;i <= n;++i) {
scanf("%s",s + 1);
insert();
}
build();
for(int i = 1;i <= m;++i) {
scanf("%s",S + 1);
work();
bfs();
}
return 0;
}