题目描述

blablabla

一开始打暴力 ，发现不好保留过程中的最大串本身 ，可以用dp，同时用指针记录下标，最后根据长度计算输出即可

太久没写dp了 犯了很多错
比如字符串读取 ，0被占用，for循环为了防止下标越界从1开始，所以要对dp00
初始化

样例

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;

int dp[N][N];

string s1,s2;
int main () {
   // scanf("%s%s", s1+1, s2+1);
   cin>>s1>>s2;
    int n1 =  s1.length(), n2 =s2.length();
    int res=0, l=0, r=0;    // l, r记录最大适配串在s1中的头尾下标
    //注意数组越界的情况
    //因为这个dp的循环要用到数组下标里  
    //既然从1开始 ，那么00就要初始化
    if(s1[0]==s2[0]){
        dp[0][0]=1; 
        res=1;
      //  a  最后一个样例    
     //   ab
    }
    for (int i=1; i<n1; i++) for (int j=1; j<n2; j++) {
        if (s1[i] == s2[j]) dp[i][j] = dp[i-1][j-1] + 1;
        else dp[i-1][j-1] = 0;
        if (dp[i][j] >= res) {
            res = max(res, dp[i][j]);
            r = i;
            l = r - dp[i][j] + 1;
        }
    }
    printf("%d\n", res);
   //  cout<<n1<<" "<<n2<<endl;
    for (int i=l; i<=r; i++) printf("%c", s1[i]);
    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla