两个字符串最长子序列问题
描述阿贝尔，挪威数学家，一生穷困潦倒，他希望以他的才华在皇家科学院谋职以支撑他的生活。他给当时的权威高斯寄去了他的研究成果，但是高斯不希望有人能超过他，不愿意收阿贝尔为徒弟。尽管阿贝尔成就极高，却在生前没有得到认可，他的生活非常贫困，死时只有27岁。就在他死后的第二天，皇家科学院给他寄去了任职信。
阿贝尔定理应用于数列判敛，所以正如你们所料，阿贝尔留下的是两个序列，希望你能计算出最长的公共子序列。
举个例子，cnblogs这个字符串中子序列有多少个呢？很显然有27个，比如其中的cb,cgs等等都是其子序列，我们可以看出子序列不见得一定是连续的，连续的那是子串。
输入
第一行为第一个字符串，第二行为第二个字符串，两个字符串的长度均不超过100
输出
输出这两个字符串的最长的公共子序列
样例输入
cnblogs
belong
样例输出
blog
#include <stdio.h>
#include <string.h>
int k = 0;
char yuri;
char *str(char *fuck,char *shit,char *temp);
int main(void)
{
char fuck;
char shit;
while(scanf("%s\n%s", fuck,shit) != EOF)
{
char temp;
if(strlen(fuck) > strlen(shit))
{
printf("%s\n", str(fuck,shit,temp));
}
else
{
printf("%s\n", str(shit,fuck,temp));
}
for(int i = 0; i < 101; i++)
{
for(int j = 0; j < 101; j++)
{
yuri = '\0';
}
}
}
return 0;
}
char *str(char *fuck,char *shit, char *temp)
{
int w = 0;
int k = 0;
int fault = 0;
for(int u = 0; u < strlen(shit); u++)
{
for(int i = u; i < strlen(shit); i++)
{
for(int j = w; j < strlen(fuck); j++)
{
if(shit == fuck)
{
temp = shit;
k++;
w = j + 1;
break;
}
}
}
temp = '\0';
strcpy(yuri,temp);
fault++;
for(int i = 0; i < k; i++)
{
temp = '\0';
}
k = 0;
w = 0;
}
char ttemp;
for(int i = 0; i < fault - 1; i++)
{
for(int j = 0; j < fault - 2; j++)
{
if(strlen(yuri) < strlen(yuri))
{
strcpy(ttemp,yuri);
strcpy(yuri,yuri);
strcpy(yuri,ttemp);
}
}
}
return yuri;
}
一直过不了这道题{:10_266:} 。求解。。。{:10_262:} #include <stdio.h>
void func(char * str1, char * str2)
{
for (char * i = str1; *i != '\0'; i++)
{
for (char * j = str2; *j != '\0'; j++)
{
if (*i == *j)
{
printf("%c", *j);
}
}
}
}
int main(int argc, char * argv[])
{
char str1[] = "cnblog";
char str2[] = "belong";
func(str1, str2);
return 0;
}
-------------------------------------------------------------------------------------------
正在运行:"E:\Program Files (x86)\QS源代码\Console - KNENE.exe"
nblog
进程退出返回值 0 (0x0) 运行时间 : 0.047 秒
按任意键继续... 动态规划思路
对于两字符串A，B，若其长度为a，b，那么其最长公共子串一定是下面4种构成方式中最长的
1、A.substr(0,a-1)和B的最长公共子串
2、A.和B.sub(0,b-1)的最长公共子串
3.若A.back()与B拥有相同的字符c,那么A.substr(0,a-1)与B.substr(0.n-1)的最长公共子串加上c后仍然是A与B的公共子串，若有多个相同，那么n尽量大时，此方法构造成的子串最长；
4.在情况3中，调换A和B的位置
#include <iostream>
#include <vector>
#include <string>
#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))
using namespace std;
string longestCommonSubstr(string s1, string s2) {
vector<vector<string>> dp(s1.size(), vector<string>(s2.size()));
int maxi = (int)s1.size() + (int)s2.size() - 1;
for (int i = 0; i < maxi; ++i) {
int maxj = min(min(i + 1, maxi - i), (int)max(s1.size(), s2.size()));
for (int j = 0; j < maxj; ++j) {
int a = min(i, (int)s1.size() - 1) - j;
int b = max(0, i - (int)s2.size() + 1) + j;
string sub1, sub2, sub3, sub4;
if (a > 0) {
sub1 = dp;
}
if (b > 0) {
sub2 = dp;
}
for (int k = b; k >= 0; --k) {
if (s1 == s2) {
if (a != 0 && k != 0) {
sub3 = dp;
}
sub3.push_back(s1);
break;
}
}
for (int k = a; k >= 0; --k) {
if (s1 == s2) {
if (k != 0 && b != 0) {
sub4 = dp;
}
sub4.push_back(s2);
break;
}
}
if (dp.size() < sub1.size()) dp = sub1;
if (dp.size() < sub2.size()) dp = sub2;
if (dp.size() < sub3.size()) dp = sub3;
if (dp.size() < sub4.size()) dp = sub4;
}
}
return dp;
}
int main() {
cout << longestCommonSubstr("cnblog", "belong");
system("pause");
} DP 这道题可以用DP做，状态转移方程是f=max(f,f)
如果两个字符相等，加上f=max(f,f+1)
条件是a==b
思想是将这个问题分成许多子结构，并求出最优的子结构，再根据子结构的答案，算出整体答案
代码如下↓↓↓
#include <bits/stdc++.h>
using namespace std;
int main()
{
char a,b;
int n=1,m=1;
while ((a=getchar())!='\n') n++;
while ((b=getchar())!='\n') m++;
n--;m--;
int f;
memset(f,0,sizeof(f));
char c;
int k=1;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=m;j++)
{
f=max(f,f);
if (a==b)
{
f=max(f,f+1);
if (f==f+1)
{
c=a;
k++;
}
}
}
}
for (int i=1;i<k;i++)
{
printf("%c",c);
}
return 0;
}
希望对楼主有帮助
（本人学生党，发帖不易，望众大佬勿喷{:10_333:}）
页:
[1]