传送门
思路：
毒瘤的字典树！
▲主要分有两个步骤：
① 日常的建树。
② 暴力地求解。
▲日常建树：过于基础，跳过。
▲重点在于如何暴力地求解而不被卡掉（DP?不存在的）
可以利用区间动规的思想，枚举文章的左右端点，判断中间区间的文章是否可以被理解。
文章的长度几乎为 INF ，直接 N2 枚举 1~INF 显然是不可能的。
而看到字典里的单词长度（模式串）长度只有 10 以下，这为暴力枚举提供了一条出路。
先看一段暴力求解的代码：
for(LL j=0;j<len;j++)//很暴力的枚举文章的右端点 for(LL k=max(j-lenth_max,-INF);k<=j;k++)//枚举文章的区间左端点，（有k=max(j-lenth_max,-INF)每次最多只有枚举10个单位长度）。 if((k==-INF||f[k])&&(find(k+1,j))) { f[j]=true;ans=j+1;break; }//注-INF = -1
find（ i ， j ) 用于查找 i~j 的文章中，是否能够成功匹配单词。
设一个 f[ j ] 表示整篇文章中，k ~ j 的文章区间能否被理解，同时要求之前文章的 f[ k ] 也要能够被理解才能更新 ans 。（ 因为要求求解能够被理解的文章最长前缀 ，不能断开 ）。
为了能够更加优化暴力，lenth_max 记录最长的单词长度。
有个小细节：在匹配成功一段区间后的 break ，跳出的只是枚举左端点的循环，而外层的枚举右端点的循环仍然继续。
标程：
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<string> #include<cstdlib> #include<stack> #include<vector> #include<queue> #include<deque> #include<map> #include<set> using namespace std; #define max(a,b) ((a)>(b)?(a):(b)) #define min(a,b) ((a)<(b)?(a):(b)) #define maxn 1000002 #define INF 1 typedef long long LL; LL n,m,len,lenth_max,ans,ch[maxn>>6][26],cnt; char s[maxn]; bool f[maxn],bo[maxn>>6]; inline LL read() { LL kr=1,xs=0; char ls; ls=getchar(); while(!isdigit(ls)) { if(!(ls^45)) kr=-1; ls=getchar(); } while(isdigit(ls)) { xs=(xs<<1)+(xs<<3)+(ls^48); ls=getchar(); } return xs*kr; } inline void insert(char *s) { LL u=0,len=strlen(s); lenth_max=max(len,lenth_max);//记录字典里最长的单词长度 for(LL i=0;i<len;i++) { LL c=s[i]-'a'; if(!ch[u][c]) ch[u][c]=++cnt; u=ch[u][c]; } bo[u]=1; } inline bool find(LL l,LL r) { LL u=0; for(LL i=l;i<=r;i++) { LL c=s[i]-'a'; if(!ch[u][c]) return false; u=ch[u][c]; } return bo[u]; } int main() { freopen("L.in","r",stdin); freopen("L.out","w",stdout); n=read();m=read(); for(LL i=1;i<=n;i++) { scanf("%s",s); insert(s); } for(LL i=1;i<=m;i++) { memset(f,false,sizeof(f));ans=0; scanf("%s",s); LL len=strlen(s); for(LL j=0;j<len;j++) for(LL k=max(j-lenth_max,-INF);k<=j;k++) if((k==-INF||f[k])&&(find(k+1,j))) { f[j]=true;ans=j+1;break; } printf("%lld ",ans); } return 0; }