求两个输入的字符串的最长公共子串
发布网友
发布时间：2022-04-22 13:42
共2个回答
热心网友
时间：2022-04-22 15:12
算法：求两个字符串的最长公共子串
原理：
（1） 将连个字符串分别以行列组成一个矩阵。
（2）。若该矩阵的节点对应的字符相同，则该节点值为1。
（3）当前字符相同节点的值 = 左上角(d[i-1, j-1])的值 +1，这样当前节点的值就是最大公用子串的长。
(s2) b c d e
(s1)
a 0 0 0 0
b 1 0 0 0
c 0 2 0 0
d 0 0 3 0
3. 结果：只需以行号和最大值为条件即可截取最大子串
C# code:
[csharp] view plaincopyprint?
public static string MyLCS(string s1, string s2)
{
if (String.IsNullOrEmpty(s1) || String.IsNullOrEmpty(s2))
{
return null;
}
else if (s1 == s2)
{
return s1;
}
int length = 0;
int end = 0;
int[,] a = new int[s1.Length, s2.Length];
for (int i = 0; i < s1.Length; i++)
{
for (int j = 0; j < s2.Length; j++)
{
int n = (i - 1 >= 0 && j - 1 >= 0) ? a[i - 1, j - 1] : 0;
a[i, j] = s1[i] == s2[j] ? 1+n : 0;
if (a[i, j] > length)
{
length = a[i,j];
end = i;
}
}
}
return s1.Substring(end - length + 1, length);
}
热心网友
时间：2022-04-22 16:30
#include<iostream>
#include<string.h>
using namespace std;
int c[1000][1000];
char str1[1000];
char str2[1000];
void func(int m,int n){
if((m<0)||(n<0)) return ;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++) c[i][j]=0;
int besti=0,bestj=0;
int count=0;
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(str1[i]==str2[j]) {
if((i==0)||(j==0)) c[i][j]=1; //增加判断是否为第一个，第一个不能再向下
else c[i][j]=c[i-1][j-1] + 1 ;
}
else c[i][j]=0;
/*
for(int i=0;i<m;i++){
for(int j=0;j<n;j++)
cout<<c[i][j]<<' ';
cout<<endl;
}
*/
for(int i=0;i<m;i++)
for(int j=0;j<n;j++)
if(c[i][j]>count) { count=c[i][j]; besti=i; bestj=j; } //查找最长子字符串
cout<<count<<endl;
if(count==0) cout<<"没有公共子串"<<endl; //公共子字符串长度为1，输出“没有公共子串”
else
for(int i=besti-count+1;i<=besti;i++) cout<<str1[i]; //否则输出靠X左边（如果多个）子字符串
}
int main() {
int m=0;
int n=0;
cin>>str1;
cin>>str2;
m=strlen(str1);
n=strlen(str2);
func(m,n);
return 0;
}
追问看不懂啊，像cout<<endl，这是什么意思。func啥意思。我是c菜鸟，才入门.
追答c++的标准输出语句,
func是自定义函数
c菜鸟还是先去好好学习基础，这个题目对你来说太难了。
