A-D 004最長共通サブシーケンス

12527 ワード
アルゴリズム2期末復習 アルゴリズム
Problem Description
シーケンスZ=とは、シーケンスX=のサブシーケンスであり、j=1,2,...,kに対してxij=zjがあるように厳密に上昇するシーケンスのみが存在する.例えばZ=はX=のサブシーケンスである.2つのシーケンスXとYが与えられ、あなたの任務はXとYの最大共通のサブシーケンスを見つけることです.つまり、ZがXのサブシーケンスであり、Yのサブシーケンスでもあるように、最も長いシーケンスZを見つけることです.
Input
入力には、複数のテストデータが含まれます.各データのセットには、200を超えない2つの文字列が含まれ、2つのシーケンスを表します.2つの文字列の間には、複数のスペースで区切られています.
Output
各入力データのセットに対して、1行を出力し、2つのシーケンスの最大共通サブシーケンスの長さを与えます.
Sample Input 
abcfbc abfcab
programming contest
abcd mnp

Sample Output 
4
2
0

問題を解く構想.
2つの文字列を文字配列s 1,s 2で格納、s 1[i]でs 1のi番目の文字、s 2[j]でs 2のj番目の文字(文字番号1から「0番目の文字」は存在しない)、s 1 iでs 1の前のi番目の文字で構成されたサブ列、s 2 jでs 2の前のj番目の文字で構成されたサブ列、MaxLen(i,j)でs 1 iとs 2 jの最長共通サブシーケンスの長さ、では、プッシュ関係は次のようになります.
if(i ==0 || j == 0) 
{
     
MaxLen(i, j) = 0 //                 0
}
else if(s1[i] == s2[j])
MaxLen(i, j) = MaxLen(i-1, j-1 ) + 1;
else
{
     
MaxLen(i, j) = Max(MaxLen(i, j-1), MaxLen(i-1, j));
}

MaxLen(i,j)=Max(MaxLen(i,j−1),MaxLen(i−1,j))という繰返し関係を証明する必要がある.反証法を用いて,MaxLen(i,j)がMaxLen(i,j−1)とMaxLen(i−1,j)よりも大きくなることは不可能であることを実証した.まず,MaxLen(i,j)がMaxLen(i−1,j)より大きいと仮定する.もしそうなら、s 1[i]が役に立つに違いない.すなわち、s 1[i]はs 1 iとs 2 jの最長共通サブシーケンスの最後の文字である.同様に,MaxLen(i,j)がMaxLen(i,j−1)よりも大きい場合には,s 2[j]がs 1 iとs 2 jの最長共通サブシーケンスの最後の文字であることも推測できる.すなわち、MaxLen(i,j)がMaxLen(i,j−1)およびMaxLen(i−1,j)よりも大きい場合、s 1[i]はs 2[j]と等しいはずである.しかし,これは本繰返し関係を適用する前提であるs 1[i]≠s 2[j]と矛盾している.したがって,MaxLen(i,j)がMaxLen(i,j−1)およびMaxLen(i−1,j)よりも大きくなることは不可能である.MaxLen(i,j)はもちろんMaxLen(i,j−1)とMaxLen(i−1,j)のいずれよりも小さくはないので,MaxLen(i,j)=Max(MaxLen(i,j−1),MaxLen(i−1,j))は必然的に成り立つ.明らかに,本問題の「状態」はs 1における位置iとs 2における位置jである.「値」はMaxLen(i,j)です.**状態の数はs 1の長さとs 2の長さの積である.2 D配列を使用して、各状態の値を格納できます.
コード#コード#
#include 
#include 
#define MAX_LEN 1000

char s1[MAX_LEN];
char s2[MAX_LEN];
int aMaxLen[MAX_LEN][MAX_LEN];

int main()
{
     
	while(scanf("%s%s", s1+1 ,s2+1 ) > 0) 
	{
     
		int nLength1 = strlen(s1+1);
		int nLength2 = strlen(s2+1);
		int nTmp;
		int i, j;
		for(i = 0;i <= nLength1; i++)
			aMaxLen[i][0] = 0;
		for(j = 0;j <= nLength2; j++)
			aMaxLen[0][j] = 0;
			
		for(i = 1;i <= nLength1;i++) 
		{
     
			for(j = 1; j <= nLength2; j++) 
			{
     
				if(s1[i] == s2[j])
					aMaxLen[i][j] = aMaxLen[i-1][j-1] + 1;
				else {
     
					int nLen1 = aMaxLen[i][j-1];
					int nLen2 = aMaxLen[i-1][j];
					if( nLen1 > nLen2 )
						aMaxLen[i][j] = nLen1;
					else
						aMaxLen[i][j] = nLen2;
				}
			}
		}
		printf("%d
", aMaxLen[nLength1][nLength2]);
	}
}
Python-ネストリストアプリケーション(未完)
Pythonタイムモジュール、プログラム実行時間(超詳細チュートリアル)を含む