LCS 最长公共字串

迷南。 2022-08-07 01:48 154阅读 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 条评论，154人围观）

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

相关阅读

相关最长公共子序列（LCS）与最长公共子串(DP)

《1》[最长公共子序列（LCS）与最长公共子串(DP)][LCS_DP] http://blog.csdn.net/u012102306/article/details/53

亦凉/ 2024年02月19日 13:24/ 0 赞/ 34 阅读

相关面试（动态规划算法之：最长公共子序列 & 最长公共子串（LCS））

收藏 1、先科普下最长公共子序列 & 最长公共子串的区别：找两个字符串的最长公共子串，这个子串要求在原字符串中是连续的。而最长公共子序列则并不要求连续。 2、最长公共

迷南。/ 2023年10月17日 14:00/ 0 赞/ 59 阅读

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

╰半夏微凉°/ 2023年07月21日 06:17/ 0 赞/ 8 阅读

相关最长公共子串 LCS 模板题（Common Subsequence ）

目录最长公共子串 LCS 模板题（Common Subsequence ）求最长公共子序列模板最长公共子串 LCS 模

￡神魔★判官ぃ/ 2023年06月01日 06:12/ 0 赞/ 9 阅读

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

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

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

相关 LCS 最长公共字串

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

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

相关 LCS 最长公共子序列

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

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

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

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

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

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

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

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

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

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

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