#UVa:10405-Longest Common Subsequence

灆洢 2012-03-27 22:31:29

此題為LCS(Longest Common Subsequence)的問題,由於本題只問長度,可只用一維陣列來求解。

P.S. 輸入要讀一整行,中間會有空白。

C++(0.012)

/*******************************************************/
/* UVa 10405 Longest Common Subsequence                */
/* Author: Maplewing [at] knightzone.studio            */
/* Version: 2012/03/27                                 */
/*******************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

int main(){
  string s1, s2;
  int LCS[1005];

  while( getline( cin, s1 ) ){
    getline( cin, s2 );

    memset( LCS, 0, sizeof(LCS) );
    for( int i = 1 ; i <= s1.length() ; i++ ){
      for( int j = s2.length() ; j >= 1 ; j-- )
        if( s1[i-1] == s2[j-1] ) LCS[j] = LCS[j-1] + 1;
      for( int j = 1 ; j <= s2.length() ; j++ ){
        if( s1[i-1] != s2[j-1] ) LCS[j] = max( LCS[j], LCS[j-1] );
      }
    }
    printf( "%d\n", LCS[s2.length()] );
  }
  return 0;
}

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料