最长公共字符串

ゞ浴缸里的玫瑰 2022-06-17 04:26 181阅读 0赞

#include <iostream>  
    #include <string>  
    #include <stack>
    #include <algorithm>
    //#include "Customer.h"
    
    using namespace std;
    
    //最长公共字符串——动态规划
    //假设需要求得字符串为str1，str2。函数f(m,n)分别为 str1[m]，str2[n]
    //结尾的公共字符串长度。
    //有以下递推公式：                                          递推边界
    //       f(m,n)=0			    str1[m]!=str2[n]            f(0,n)=0;
    //       f(m,n)=f(m-1,n-1)+1    str1[m]!=str2[n]            f(m,0)=0;
    int main()
    {
    	string str1;
    	string str2;
    	getline(cin, str1);
    	getline(cin, str2);
    
    	int c[100][100] = { 0 };
    	for (int i = 0; i < str1.length(); i++)
    	{
    		for (int j = 0; j < str2.length(); 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;
    		}
    	}
    
    	int besti = 0, bestj = 0;
    	int count = 0;
    	for (int i = 0; i < str1.length(); i++)
    	{
    		for (int j = 0; j < str2.length(); j++)
    		{
    			if (c[i][j] > count)
    			{
    				count = c[i][j];
    				besti = i;
    				bestj = j;
    			}
    		} 
    	}
    	cout << "最长公共字符串长度： " << count << endl;
    	cout << "str1公共子串结束下标： " << besti << endl;
    	cout << "str2公共子串结束下标： " << bestj << endl;
    	return 0;
    }

发表评论取消回复

表情：

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

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

相关阅读

相关 LeetCode_字符串_简单_14.最长公共前缀

目录 1.题目 2.思路 3.代码实现（Java） 1.题目编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符

水深无声/ 2023年10月06日 18:32/ 0 赞/ 42 阅读

相关 LeetCode 14.最长公共前缀（字符串）

上一篇博客：[Leetcode 13.罗马数字转整数（字符串）][Leetcode 13.] > 写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepte

素颜马尾好姑娘i/ 2022年11月27日 15:59/ 0 赞/ 170 阅读

相关字符串----最长公共前缀

/ 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。示例 1：输入：strs = ["flower","flow

布满荆棘的人生/ 2022年11月19日 01:15/ 0 赞/ 247 阅读

相关最长公共前缀

题目：编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 “”。示例 1：输入：strs = \[“flower”,“flow”

缺乏、安全感/ 2022年10月26日 12:57/ 0 赞/ 208 阅读

相关最长公共前缀

[lintcode最长公共前缀][lintcode] class Solution { public: / @pa

短命女/ 2022年09月24日 12:27/ 0 赞/ 197 阅读

相关字符串应用之最长公共子序列和最长公共子串

最长公共子序列 Xm表示X串的前m个字符，即x0,x1...xm−1 LCS(Xm,Yn)即X的前m个字符和Y的前n个字符的最长公共子序列。动规方程如下：

迷南。/ 2022年07月12日 00:25/ 0 赞/ 215 阅读

相关最长公共字符串

include <iostream> include <string> include <stack> include <algorit

ゞ浴缸里的玫瑰/ 2022年06月17日 04:26/ 0 赞/ 182 阅读

相关数据结构 - 字符串 - 最长公共子序列 + 最长公共子字符串 - 动态规划

最长公共子序列 ![最长公共子序列][SouthEast] / 最长公共子序列参考链接：http://blog.csdn.net/bi

谁践踏了优雅/ 2022年06月01日 02:42/ 0 赞/ 202 阅读

相关 [字符串] 14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 `""`。 class Solution \{ public: strin

左手的ㄟ右手/ 2021年12月09日 05:11/ 0 赞/ 271 阅读

相关【搞定算法】字符串的最长公共子串和最长公共子序列

目录： 1、求两个字符串的最长公共子串 2、求两个字符串的最长公共子序列动态规划实现求两个字符串的最长公共子序列的长度 ------------

骑猪看日落/ 2021年11月09日 23:38/ 0 赞/ 337 阅读