2つの文字列の最も長い共通の連続するサブシーケンスの長さを求めます

3244 ワード

2017年に全国統一模擬筆記試験(第2場)のプログラミング問題の集合の1つの問題を募集して、2つの文字列の最も長い公共の連続するサブシーケンスの長さを求めます
タイトルアドレス第一題
以下はc++コードです
#include 
#define ll long long
#define inf 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
int m[100][100];
int main(){//freopen("1.txt","r",stdin);
    int i,j,k1,k2,n,ans=0,max;
    string s1,s2;
    getline(cin,s1);
    getline(cin,s2);
    k1=s1.size();
    k2=s2.size();
    mem(m,0);
    for(i=0;ifor(j=0;jif(s1[i]==s2[j])m[i][j]=1;
    for(i=0;imax=0;
        for(j=0;jif(m[i+j][j]==1)max++;
            else max=0;
            if(max>ans)ans=max;
        }
    }//                     
    for(i=0;imax=0;
        for(j=0;jif(m[j][i+j]==1)max++;
            else max=0;
            if(max>ans)ans=max;
        }
    }//                     
    printf("%d
"
,ans); /* for(i=0;i return 0; }

大体の考え方.
2つの文字列str 1とstr 2がそれぞれmとnの長さであると仮定すると、m*nのマトリクスmatrixが構築され、
   matrix[i][j]==1     str1  i    str2  j     , 0    。

       matrix      1         str1 str2            

例えばstr 1:abcde str 2:abgde斜線上で連続する1の最大個数は2であるため、最長共通連続サブ列長は2である
  matrix = [ 1  0  0  0  0 

             0  1  0  0  0

             0  0  0  0  0

             0  0  0  1  0

             0  0  0  0  1 ]