首页 > 代码库 > 【USACO 2.3】The Longest Prefix
【USACO 2.3】The Longest Prefix
题意：
给你一个少于200000的字符串，求最长的可以划分为给定词典里的单词的前缀。
题解：
dp[i]表示第i位结尾的前缀是否可行，然后枚举每一位如果dp[i-1]==1，枚举所有单词，匹配成功的单词，则dp[i+单词长度-1]=1。
注意读入单词是以‘.‘作为结束，而读入字符串，有可能是很多行，要拼接一下。
/*TASK:prefixLANG:C++*/#include<cstdio>#include<cstring>#include<algorithm>using namespace std;char dic[205][15],s[200005],ts[80];int cnt;bool dp[200005];int ans;int main(){ freopen("prefix.in","r",stdin); freopen("prefix.out","w",stdout); while(scanf("%s",dic[cnt]),dic[cnt][0]!=‘.‘)cnt++; while(~scanf("%s",ts))strcat(s,ts); for(int i=0;s[i];i++){ if(i&&!dp[i-1])continue; for(int j=0;j<cnt;j++){ int k=0,ok=1; for(;dic[j][k];k++) if(dic[j][k]!=s[i+k]){ok=0;break;} if(ok){dp[i+k-1]=1;ans=max(ans,i+k);} } } printf("%d\n",ans);}
【USACO 2.3】The Longest Prefix
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。