算法1

(trie树+DP) $O(n)$

这里说一下思路：

集合：f[i]表示以i结尾的最长前缀长度.

转移：这里设最长前缀为A,和A的其中一个前缀S,则A=S+p[i](p[i]是题目中给的集合P中的字符串长度),
所以A可以从S处转移而来,S=A-p[i],所以f[A]=f[A-p[i]]+p[i],由于我们设了i为最长前缀长度,所以
状态转移方程为f[i]=f[i-j]+j,j为p[]的长度.

注意:这里转移要看一下S的前缀中是否有p[],查一下trie即可.

C++ 代码

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

using namespace std;

const int N=2e5+10,M=2e4;

string s[300];
char a[N];
int n,len=1;
int p[N][30],idx;
int cnt[N];
int f[N];
int maxv,m;
string t[N];

void build(string u)//构造trie树
{
    int root=0;
    for(int i=0;i<u.size();i++)
    {
        int x=u[i]-'A';
        if(!p[root][x])
        p[root][x]=++idx;

        root=p[root][x];

    }
    cnt[root]++;
    return ;
}

bool query(string t)//访问每个字符串是否存在
{
    int root=0;
    for(int i=0;i<t.size();i++)
    {
        int temp=t[i]-'A';
        if(p[root][temp]) root=p[root][temp];
        else return false;
    }

    return cnt[root];
}

bool pan(int x,int y)//判断当前p[]是否在S的前缀当中
{
    string s;
    int i=y,j=x;
    while(i)
    {
        s+=a[j];
        i--;
        j--;
    }
    reverse(s.begin(),s.end());

    return query(s);
}

int main()
{
    while(cin>>s[n]&&s[n][0]!='.') n++;n-=1;

    //读入字符
    while(cin>>t[m]) m++;

    for(int i=0;i<m;i++)
    for(int j=0;j<t[i].size();j++) a[len++]=t[i][j];
    len-=1;

    for(int i=0;i<=n;i++) build(s[i]);//建立trie树

    for(int i=1;i<=len;i++)
    for(int j=1;j<=10;j++)
    if(i>=j&&pan(i,j)) {f[i]=max(f[i],f[i-j]+j);}//取i的前j个字符

    int maxv=0;            //这里要判断一下只有i==f[i]时才能记录
    for(int i=1;i<=len;i++) if(i==f[i]) maxv=max(maxv,f[i]);

    cout<<maxv;
    return 0;
}