1. 题目

传送门＝￣ω￣＝

2. 题解

[2017 年 5 月 16 日]
听说能用 trie 树做。
记忆化非递归式深搜。
设 $book(i)$表示状态 $i$是否达到过（即前 $i$个字符都成功分解）。
枚举子串即可。

（在这份代码下面有更优做法！）

代码：

#include <bits/stdc++.h>
using namespace std;
int n,subl[205],strl;
bool book[200005];
char sub[205][15],str[200005];
void dfs(int k)
{
    if(book[k])return;book[k]=1;
    for(int i=1,f=0;i<n;i++,f=0)
    {
        for(int j=0;j<subl[i];j++)if(sub[i][j]!=str[k+j]||k+j>=strl){f=1;break;}
        if(!f)dfs(k+subl[i]);
    }
}
int main()
{
    while(scanf("%s",sub[++n]),strcmp(sub[n],".")!=0)subl[n]=strlen(sub[n]);
    do{str[strl]=getchar();if(isupper(str[strl]))strl++;}while(str[strl]!=EOF);
    dfs(0);
    for(int i=strl;i>=0;i--)if(book[i]){printf("%d\n",i);return 0;}
}

[2017 年 5 月 26 日更新]
额，昨天试着把上面的代码交到 codevs 上结果RE了
经过检查，发现是递归爆栈了。
于是开始写递推做法，不用 dfs。。。
加了个优化，就是把子串按照长度从小到大排序，如果排前面的因过长而不符合条件，那么后面的也都不符合了。
这样以来最慢的点是 5ms（codevs，luogu 最慢是 4ms），比 trie 树还快（dalao 们说 trie 树 49ms）。
代码也短＝￣ω￣＝

代码：

#include <bits/stdc++.h>
using namespace std;
int n,strl;
bool book[200005];
char str[200005];
struct st{char s[15];int l;}sub[205];
bool cmp(st a,st b){return a.l<b.l;}
int main()
{
    while(scanf("%s",sub[++n].s),strcmp(sub[n].s,".")!=0)
        sub[n].l=strlen(sub[n].s);
    do{str[strl]=getchar();if(isupper(str[strl]))strl++;}while(str[strl]!=EOF);
    n--,book[0]=1,sort(sub+1,sub+1+n,cmp);
    for(int i=1;i<=strl;i++)
        for(int j=1;j<=n&&sub[j].l<=i;j++)
            if(book[i-sub[j].l])
            {
                for(int k=0;k<sub[j].l;k++)
                    if(sub[j].s[k]!=str[i-sub[j].l+k]){book[i]=1;break;}
                if(book[i]^=1)break;
            }
    for(int i=strl;i>=0;i--)if(book[i]){printf("%d\n",i);break;}
    return 0;
}