很久没做dp了，，然后开始看到这题目都不知道该怎么下手了；其实这是一道dp的典型题，每次都可以有多种选择但是不到最后是不知道最优解的。 令dp[i]表示以i为起点的最长前缀，然后dp[i]=max(dp[i+len[j]]+len[j]) 当然i+len[j]要小于原字符串的长度。
代码如下：
/*ID:15674811LANG:C++PROG:prefix*/;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<cnt;i++)len[i]=strlen(str[i]);int dp[220000];memset(dp,0,sizeof(dp));char tmp[220000];char s[110];while(fin>>s){strcat(tmp,s);}int k=strlen(tmp);for(int i=k-1;i>=0;i–)for(int j=0;j<cnt;j++){int d;if(i+len[j]>k)continue;for(d=i;d<i+len[j];d++)if(tmp[d]!=str[j][d-i])break;if(d>=i+len[j])dp[i]=max(dp[i+len[j]]+len[j],dp[i]);}fout<<dp[0]<<endl; return 0;}
就是去旅行。牵着彼此的手，
