本文共 699 字，大约阅读时间需要 2 分钟。
很久没做dp了，然后开始看到这题目都不知道该怎么下手了；其实这是一道dp的典型题，每次都可以有多种选择但是不到最后是不知道最优解的。
令dp[i]表示以i为起点的最长前缀，然后dp[i]=max(dp[i+len[j]]+len[j])
当然i+len[j]要小于原字符串的长度。
代码如下：
/*ID:15674811LANG:C++PROG:prefix*/#include #include #include #include #include #include using namespace std;int main(){ ofstream fout("prefix.out"); ifstream fin("prefix.in"); ///ifstream fin("lkl.txt"); char str[220][15]; int cnt=0; while(true) { fin>>str[cnt]; if(str[cnt][0]=='.') break; cnt++; } int len[220]; for(int i=0;i >s) { strcat(tmp,s); } int k=strlen(tmp); for(int i=k-1;i>=0;i--) for(int j=0;j k) continue; for(d=i;d =i+len[j]) dp[i]=max(dp[i+len[j]]+len[j],dp[i]); } fout< <
转载地址：http://durfb.baihongyu.com/