首页 > 其他 > 详细

(基础)最长公共字串

时间:2020-02-25 15:46:56      阅读:52      评论:0      收藏:0      [点我收藏+]

输入两个字符串,求最长公共字串长度,该字串的每个字符必须在这两个字符串都出现过,并且后出现的字符不能先于先出现的字符。

输入:

a b c d e f g h

a c j i f a b h h

输出:

4

技术分享图片

 

 

#include <stdio.h>
#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
const double PI=acos(-1.0);
const int inf=0x7fffffff;
int a[105][105];
int dp[105][105];
int n,m,mx,sum; 

int main(){
    string a,b;
    cin>>a>>b;
    n=a.length();
    m=b.length();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i-1]==b[j-1]){            //i代表循环到a中所处字符的位置,j代表循环到b中所处字符的位置 
                dp[i][j]=dp[i-1][j-1]+1;   //a串中的i位置可以和b串中的j位置字符匹配,则可以沿着上一次最大字串长+1 
            }
            else{
                dp[i][j]=max(dp[i-1][j],dp[i][j-1]); //不匹配。则取该行前一个元素和该列前一个元素的最大值。 
            }
        }
    } 
    cout<<dp[n][m];
    return 0; 
}

Someone once said :

Don‘t be afraid if you find a crack on your soul,because that‘ll be where the sunshine comes in.

(基础)最长公共字串

原文:https://www.cnblogs.com/xusi/p/12361872.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!