題意很簡單，找出2個字符串的最長公共字串，并輸出所有解。
前一個問題很簡單，后面一個問題有點小麻煩
首先，需要在狀態(tài)轉(zhuǎn)移時記錄下所有的最優(yōu)決策，我是用一個vector來記錄的
可以發(fā)現(xiàn)，解的結(jié)構(gòu)是一個階段圖，這樣就可以用DP來構(gòu)造解，當然狀態(tài)是一個集合。
DP其實很靈活，狀態(tài)不僅僅可以是一個數(shù)字、一個字符串，也可以是對象等。像這道題狀態(tài)轉(zhuǎn)移過程就是集合的合并，應該用左偏樹或者spaly的，我偷懶，直接用set了- -結(jié)果跑了800MS，汗。。
1
# include <iostream>
2# include <vector>
3# include <cstring>
4# include <set>
5# include <string>
6using namespace std;
7int dp[100][100];
8vector<int> path[100][100];
9char str1[100],str2[100];
10set<string> ans[100][100];
11# define encode(a,b) (((a)<<7)|(b))
12int solve(int p1,int p2)
13
{
14
if(p1<=0||p2<=0) return 0;
15 else if(dp[p1][p2]!=-1) return dp[p1][p2];
16 else
17
{
18 if(str1[p1]==str2[p2])
19 {
20 dp[p1][p2]=solve(p1-1,p2-1)+1;
21 path[p1][p2].push_back(encode(p1-1,p2-1));
22
}
23 else
24 {
25 if(solve(p1-1,p2)==solve(p1,p2-1))
26 {
27 dp[p1][p2]=solve(p1-1,p2);
28 path[p1][p2].push_back(encode(p1-1,p2));
29 path[p1][p2].push_back(encode(p1,p2-1));
30 }
31 else if(solve(p1-1,p2)>solve(p1,p2-1))
32 {
33 dp[p1][p2]=solve(p1-1,p2);
34 path[p1][p2].push_back(encode(p1-1,p2));
35 }
36 else
37 {
38 dp[p1][p2]=solve(p1,p2-1);
39 path[p1][p2].push_back(encode(p1,p2-1));
40 }
41 }
42 return dp[p1][p2];
43 }
44
}
45void makeans(int p1,int p2,int len)
46{
47 if(len==0) ans[p1][p2].insert(string(""));
48 else if(ans[p1][p2].size()!=0) return;
49 else
50 {
51 for(int i=0;i<path[p1][p2].size();i++)
52 {
53 int t1=path[p1][p2][i]>>7,t2=path[p1][p2][i]&127;
54 if(t1==p1-1&&t2==p2-1)
55 {
56 makeans(p1-1,p2-1,len-1);
57 for(set<string>::iterator it=ans[p1-1][p2-1].begin();it!=ans[p1-1][p2-1].end();it++)
58 ans[p1][p2].insert(*it+str1[p1]);
59 }
60 else if(t1==p1-1)
61 {
62 makeans(p1-1,p2,len);
63 ans[p1][p2].insert(ans[p1-1][p2].begin(),ans[p1-1][p2].end());
64 }
65 else
66 {
67 makeans(p1,p2-1,len);
68 ans[p1][p2].insert(ans[p1][p2-1].begin(),ans[p1][p2-1].end());
69 }
70 }
71 }
72}
73int main()
74{
75 memset(dp,-1,sizeof(dp));
76 cin>>str1+1>>str2+1;
77 makeans(strlen(str1+1),strlen(str2+1),solve(strlen(str1+1),strlen(str2+1)));
78 for(set<string>::iterator it=ans[strlen(str1+1)][strlen(str2+1)].begin();it!=ans[strlen(str1+1)][strlen(str2+1)].end();it++)
79 cout<<*it<<endl;
80 //system("pause");
81 return 0;
82}
83