LCS 最长公共字串

迷南。 2022-08-07 01:48 107阅读 0赞

\#include<stdio.h>  
\#include<string.h>  
  
  
int c\[10000\]\[10000\];  
char str1\[10000\];  
char str2\[10000\];  
  
  
void func(int m,int n) \{  
if(m < 0 || n < 0)  
return ;  
int i,j;  
for(i = 0 ; i < m ; i++)  
for(j = 0 ;j < n;j++)  
c\[i\]\[j\] = 0;  
int besti = 0,bestj = 0;  
int count = 0;  
  
  
for(i = 0; i < m;i++)  
for(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(i = 0;i < m ;i++)  
for(j = 0; j < n ;j++)  
if(c\[i\]\[j\] > count)\{  
count = c\[i\]\[j\];  
besti = i;  
bestj = j;  
\}  
  
  
for(i = 0 ; i < m ;i++)  
\{  
for(j = 0 ; j < n;j++)  
\{  
printf("%d ",c\[i\]\[j\]);  
\}  
printf("\\n");  
\}  
  
  
if(count > 0)  
for(i = besti - count + 1; i <= besti;i++)  
printf("%c",str1\[i\]);  
  
\}  
int main()\{  
int m = 0;  
int n = 0;  
scanf("%s",&str1);  
scanf("%s",&str2);  
m = strlen(str1);  
n = strlen(str2);  
func(m,n);  
scanf("%d");  
\}

发表评论取消回复

表情：

评论列表（有 0 条评论，107人围观）

还没有评论，来说两句吧...

相关阅读

相关最长公共子序列（LCS）

最长公共子序列（LCS） problem [leetcode: 1035. 不相交的线][leetcode_ 1035.] > dp\[i\]\[j\]：nums

朴灿烈づ我的快乐病毒、/ 2022年10月14日 13:54/ 0 赞/ 107 阅读

相关最长公共子序列（LCS）

这两天编程涉及到求两个字符串的最长公共子序列问题，于是便重新复习之前一直没弄懂的最长公共子序列算法，也算是弄懂了一点。算法分析：采用动态规划方法来解决问题，将最长公共子

分手后的思念是犯贱/ 2022年09月29日 15:52/ 0 赞/ 118 阅读

相关最长公共字串（动态规划）

【题目】给定两个字符串 str1 和 str2，返回两个字符串的最长公共子串。【举例】 str1 =“1AD12345CD ”， str2 =“12345E

落日映苍穹つ/ 2022年08月18日 02:19/ 0 赞/ 119 阅读

相关 LCS 最长公共字串

\include<stdio.h> \include<string.h> int c\[10000\]\[10000\]; char str1\[100

迷南。/ 2022年08月07日 01:48/ 0 赞/ 108 阅读

相关 LCS 最长公共子序列

首先要明白什么是子序列，什么是子串；设：主串长度为n；子序列：从主串中抽出少于n的元素组成的序列（这些抽出的元素比一定是连续的他们的相对位置不变）；

绝地灬酷狼/ 2022年08月03日 14:57/ 0 赞/ 115 阅读

相关 Common Subsequence（最长公共字串-动态规划）

Common Subsequence Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/3276

红太狼/ 2022年08月02日 14:43/ 0 赞/ 105 阅读

相关 Java——最长公共子串问题LCS

Java——最长公共子串问题LCS 求最长公共子序列（Longest Common Subsequence, LCS）：如果字符串一的所有字符按其在字符串中的顺序出现在

秒速五厘米/ 2022年06月17日 00:07/ 0 赞/ 175 阅读

相关最长公共子序列Lcs

1.给出两个字符串A B，求A与B的最长公共子序列的长度（子序列不要求是连续的）。 2.给出两个字符串A B，求A与B的最长公共子序列子串（子序列不要求是连续的）。

浅浅的花香味﹌/ 2022年06月12日 10:55/ 0 赞/ 127 阅读

相关 LCS/最长公共子序列/最长公共子串实现 Python/Java

参考 [http://blog.csdn.net/u012102306/article/details/53184446][http_blog.csdn.net_u012

阳光穿透心脏的1/2处/ 2022年05月29日 04:40/ 0 赞/ 164 阅读

相关 LCS（最长公共子串）系列问题

问题一探索递归模式下，电脑最长计算的长度情况。（我也很神秘，为什么老师要出这种问题。。。）就是不断修改下面的`n`，来看看数值就知道了~ include

绝地灬酷狼/ 2022年05月08日 03:58/ 0 赞/ 120 阅读