POJ1934 (Trip)[LCS，DFS]

发表于 | 更新于 | | 阅读次数：

题目链接：http://poj.org/problem?id=1934

先用动态规划求两个字符串的最长公共子序列的保存在dp[i][j];dp[i][j]表示s1字符串1到i和s2字符串1到j的最长公共子序列的长度

然后用两个变量last1[i][j],last2[i][j]来分别保存字符j(a的序号为0，b的序号为1，…..z的序号为25)在字符串1-i中出现的最大标号，要是字符j没有出现,则last[i][j]= 0;

然后从两个字符串的长度len1和len2开始枚举a—z字符,比如开始 t1 = last1[len1][0], t2 = last2[len2][0]表示a在s1字符串1—len1的最大下标为t1, 在s2字符串1–len2的最大下标为t2，那么若dp[t1][t2] 的值为s1和s2的最大公共子序列长度cnt则表示这个字符符合，保存起来，否则枚举下一个字符b。若满足情况的话，在继续在t1-1 和 t2 - 1 符合最大公共子序列为cnt - 1的字符串保存，如此循环，知道到达最长公共子序列为0时结束。把保存的字符串放入set集合里面，让它按字典序排序。
引用自https://blog.csdn.net/xiaoxiaoluo/article/details/8169533

动态规划具有重叠子问题的特性，dp数组只保留了相当有限的信息。为了求出所有满足条件的子序列，必须另开一个数组维护信息。
另外实现上有一个小细节出错了，就是s[i]下标从0开始，dp[i][j]下标从1开始，一开始混在一起了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <set>
#include <iostream>
using namespace std;
char s1[100],s2[100];
int f[81][81];
int last1[81][26];
int last2[81][26];
set<string> ans;
char str[100];
int t=0;
void dfs(int p1,int p2,int x) {
	if(x==0) {
		string ss=str+1;	
		ans.insert(ss);
		return ;
	}
	for(int i=0;i<26;i++) {
		int t1=last1[p1][i];
		int t2=last2[p2][i];
		if(x==f[t1][t2]) {
			str[x]=i+'a';
			dfs(t1-1,t2-1,x-1);
		}
	}
}
int main() {
	scanf("%s",s1);
	scanf("%s",s2);
	int l1=strlen(s1);
	int l2=strlen(s2);
	int mx=0;
	for(int i=1;i<=l1;i++) {
		for(int j=1;j<=l2;j++) {
			if(s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1]+1;
			else f[i][j]=max(f[i][j-1],f[i-1][j]);
			mx=max(f[i][j],mx);
		}
	}
	for(int i=1;i<=l1;i++)
		for(int j=0;j<26;j++) {
			if(s1[i-1]=='a'+j) last1[i][j]=i;
			else last1[i][j]=last1[i-1][j];
		}
	for(int i=1;i<=l2;i++)
		for(int j=0;j<26;j++) {
			if(s2[i-1]=='a'+j) last2[i][j]=i;
			else last2[i][j]=last2[i-1][j];
		}
	dfs(l1,l2,mx);
	set<string>::iterator it;
	for(it=ans.begin();it!=ans.end();it++) {
		cout << (*it) << endl;
	}
}