嗯嗯,这题啊,正解应该是trie树。
不过如果你够大佬,比如xzy,就可以用dfs轻松5msA掉。
而本蒟蒻的trie树不仅代码量>大佬xzy,而且还用了44ms。
真是失败。
好吧,思路是建立一棵trie树,然后对于字符串中的每一个字符,如果其前一个字符是某个单词的结尾,就深入这个trie树,并标记找到的所有单词结尾。注意最后一个字符也要特判。
代码:

#include<iostream>
#include<cstdio>
#include<climits>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
using namespace std;
char s[77],ss[200005];
int a[20005][28],tot,ans,ll;
bool f[200005],val[2005];
void tri(){
    int i,j,l=strlen(s),from=0,sum;
    for(i=0;i<l;i++){
        sum=s[i]-'A'+1;
        if(a[from][sum])from=a[from][sum];
        else {tot++;a[from][sum]=tot;from=tot;}
    }
    val[from]=1;
}
void init(int x){
    int i,j,from=0,sum;
    for(i=x;i<ll;i++){
        sum=ss[i]-'A'+1;
        if(a[from][sum])from=a[from][sum];
        else break;
        if(val[from])f[i]=1;
    }
}
int main()
{
    int i,j;
    while(1){scanf("%s",s);if(s[0]=='.')break;tri();}
    while(scanf("%s",s)!=EOF)strcat(ss,s);
    ll=strlen(ss);init(0);
    for(i=1;i<ll;i++)if(f[i-1]){init(i);ans=i;}
    if(f[ll-1])ans=ll;
    printf("%d",ans);
    return 0;
}
分类: 所有

litble

苟...苟活者在淡红的血色中,会依稀看见微茫的希望

3 条评论

boshi · 2017年5月27日 3:58 下午

%%%%%%%%%%*2333333333333333333333333333333333333333333333333

konnyakuxzy · 2017年5月26日 9:46 下午

Orz咱kb大佬有个习惯就是

#define 蒟蒻 大佬
#define 大佬 蒟蒻
//上面的代码完全是不能编译的

Orz,kb太强啦
%%%%%%%%%%*$2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2^{2}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$

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

[…] KB的做法 […]

发表评论

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

你是机器人吗? =。= *