继 KB 用 TRIE 树、XZY 用 DFS 将此题在 5ms 内 AC 后，本人也跟风用 KMP 来 AC 了此题，耗时 258ms。我真是太弱了。垃圾地我竟然写了 72 行！而且还是最慢的。。。

题意：用给定的一些字符串拼凑新的字符串，给定的字符串的可被拼凑的最长前缀的长度是多少？有约 200 个长度 10 以内的给定字符串和一个长度 200000 以内的目标串。字符串可以重复使用。

思路：此题思路较多:

1.XZY: 考虑到字符串真正用到的部分较少，匹配时失配几率较大，所以可以使用搜索去逼近并达到最长前缀。

(LINK:)XZY 的做法

2.KB: 采用 TRIE 树，应该为本题的正解，但是代码量大，在数据水和常数大的局限下速度也不如搜索快，次解法可以自行百度。

(LINK:)KB 的做法

3. 我：注意到 O(200×200000×k) 的复杂度是可行的，所以可以对每一个小字符串对原数组进行 KMP 匹配，求得每个字符串可以覆盖目标串的部分，再用动态规划求出目标串的最长前缀无重叠覆盖面积。虽然很垃圾，但是 AC 还是没有问题的。

#include <iostream>
#include <cstdio>
#include <cstring>

#define MX 200001

using namespace std;

int nxt[202][12],lens[201];
char have[MX][201],str[201][11],tar[MX];
int n,lentar,f[MX];

void input()
{
    int len1,len2=0;
    char ch;
    for(n=1;; n++)
    {
        ch=getchar(),len1=0;
        while(ch<'A'||ch>'Z'){if(ch=='.')goto xxxxx;ch=getchar();}
        while(ch>='A'&&ch<='Z')str[n][len1++]=ch,ch=getchar();
    }
    xxxxx:;
    n--;
    while(cin>>ch){if(ch<'A'||ch>'Z')continue;tar[len2++]=ch;}
    lentar=strlen(tar);
    for(int i=1;i<=n;i++)lens[i]=strlen(str[i]);
}

void getnext(char *s,int len,int *dis)
{
    dis[0]=0;
    int i,j=0;
    for(i=1;i<len;i++)
    {
        while(j>0&&s[j]!=s[i])j=dis[j-1];
        if(s[j]==s[i])j++;
        dis[i]=j;
    }
}

void kmp(char *t,char *s,int tlen,int slen,int *nt,int snum)
{
    int i=0,j=0;
    while(i<tlen&&j<slen)
    {
        if(t[i]==s[j])i++,j++;
        else if(j==0)i++;
        else j=nt[j-1];
        if(j==slen)have[i-1][0]++,have[i-1][have[i-1][0]]=lens[snum],j=nt[j-1];
    }
}

void work()
{
    for(int i=1;i<=n;i++)getnext(str[i],strlen(str[i]),nxt[i]);
    for(int i=1;i<=n;i++)kmp(tar,str[i],strlen(tar),strlen(str[i]),nxt[i],i);
    for(int i=0;i<lentar;i++)
        for(int j=1;j<=have[i][0];j++)
            if(i-have[i][j]==-1){f[i]=1;break;}
            else if(f[i-have[i][j]]){f[i]=1;break;}
    for(int i=lentar-1;i>=0;i--)if(f[i]){cout<<i+1<<endl;return;}
    cout<<0<<endl;
}

int main()
{
    input();
    work();
    return 0;
}