最长公共子串

2018-07-11  本文已影响6人  小幸运Q

跟子序列的方法很像,但是只需要dp[i][j]=dp[i-1][j-1]+1;,因为子串必须连续,所以不需要else的内容。

#include <bits/stdc++.h>
using namespace std;
#define N 1000
int dp[N][N]={0};
char a[N];
char b[N];
int main(){
  int i,j;
  int max_length=0;
  scanf("%s %s",&a,&b);
  int len_a=strlen(a);
  int len_b=strlen(b);
  int end_a=0;
  int end_b=0;
  for(i=1;i<len_a;i++){
    for(j=1;j<len_b;j++){
      if(a[i-1]==b[j-1]){
        dp[i][j]=dp[i-1][j-1]+1;
        if(max_length<dp[i][j]){
          max_length=dp[i][j];
          end_a=i-1;
          end_b=j-1;
        }
      }
    }
  }
  cout<<"max:"<<max_length<<endl;
  cout<<"end:"<<end_a<<"  "<<end_b<<endl;
}
上一篇 下一篇

猜你喜欢

热点阅读