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;
}

分享至ヾ(≧∇≦*)ゝ:
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

1 条评论

【题解】 最长前缀 (CodeVS2052) boshi – K-XZY · 2017年5月26日 7:42 下午

[…] XZY的做法 […]

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *