首页 > 代码库 > 求最长公共子串（串）
求最长公共子串（串）
题目描述
求采用顺序结构存储的串s和串t的一个最长公共子串，若没有则输出false，若最长的有多个则输出最先出现的那一串。
输入要求
输入两个字符串
输出要求
输出公共子串
假如输入
abcdef
adbcef应当输出
bc思路：
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
结果：只需以行号和最大值为条件即可截取最大子串
#include<iostream>
#include<algorithm>
#include <vector>
#include<string.h>
#include<ctype.h>
#include<math.h>
#include<stdlib.h>
using namespace std;
void fun();
int main()
{
fun();
return 0;
}
void fun()
{
char str0[100],str1[100],dest[100];
gets(str0);
gets(str1);
if(!strcmp(str0,str1))
puts(str1);
else
{
memset(dest,'\0',sizeof(dest));
int i,j,n,length=0,end=0,arr[100][100];
for(i=0;str0[i];i++)
{
for(j=0;str1[j];j++)
{
n = (i - 1 >= 0 && j - 1 >= 0) ? arr[i - 1][ j - 1] : 0;
arr[i][j] = str0[i] == str1[j] ? 1 + n : 0;
if (arr[i][j] > length)
{
length = arr[i][j];
end = i;
}
}
}
if(length==0)
cout<<"false"<<endl;
else
{
strncpy(dest,&str0[end - length + 1],length);
cout<<dest<<endl;
}
}
}求最长公共子串（串）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。