LCS POJ 1458 Common Subsequence
6766 단어 sequence
제목 전송문
1 /* 2 LCS(Longest Common Subsequence) ： 3 ：dp[i+1][j+1] = dp[i][j] + 1; (s[i] == t[i]) 4 dp[i+1][j+1] = max (dp[i][j+1], dp[i+1][j]); (s[i] != t[i]) 5 */ 6 #include <cstdio> 7 #include <cstring> 8 #include <iostream> 9 #include <string> 10 #include <algorithm> 11 using namespace std; 12 13 const int MAXN = 3e2 + 10; 14 const int INF = 0x3f3f3f3f; 15 16 char s[MAXN]; 17 char t[MAXN]; 18 int dp[MAXN][MAXN]; 19 20 void LCS(int len1, int len2) 21 { 22 for (int i=0; i<len1; ++i) 23 { 24 for (int j=0; j<len2; ++j) 25 { 26 if (s[i] == t[j]) 27 { 28 dp[i+1][j+1] = dp[i][j] + 1; 29 } 30 else 31 { 32 dp[i+1][j+1] = max (dp[i][j+1], dp[i+1][j]); 33 } 34 } 35 } 36 } 37 38 int main(void) //POJ 1458 Common Subsequence 39 { 40 #ifndef ONLINE_JUDGE 41 freopen ("LCS.in", "r", stdin); 42 #endif 43 44 while (~scanf ("%s%s", &s, &t)) 45 { 46 memset (dp, 0, sizeof (dp)); 47 int len1 = strlen (s); 48 int len2 = strlen (t); 49 50 LCS (len1, len2); 51 printf ("%d
", dp[len1][len2]); 52 } 53 54 return 0; 55 }이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
POJ 2442 SequenceSequence Time Limit: 6000MS Memory Limit: 65536K Total Submissions: 6120 Accepted: 1897 Description Given m sequences, e...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
