2つの文字列の最も長い共通の連続するサブシーケンスの長さを求めます
3244 ワード
2017年に全国統一模擬筆記試験(第2場)のプログラミング問題の集合の1つの問題を募集して、2つの文字列の最も長い公共の連続するサブシーケンスの長さを求めます
タイトルアドレス第一題
以下はc++コードです
大体の考え方.
2つの文字列str 1とstr 2がそれぞれmとnの長さであると仮定すると、m*nのマトリクスmatrixが構築され、
例えばstr 1:abcde str 2:abgde斜線上で連続する1の最大個数は2であるため、最長共通連続サブ列長は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 ]