LCS
Z RNO-Wiki
(Różnice między wersjami)
(Nowa strona: <table width="100%"> <tr> <td valign="top"> <source lang="cpp"> #include<iostream> #include<string> using namespace std; string a,b; int lcs[1001][1001]; int main(void) { cin >> a; ...) |
m |
||
Linia 23: | Linia 23: | ||
{ | { | ||
− | if ( a[i-1] == b[j-1] ) // a[i-1] = i-ta litera | + | if ( a[i-1] == b[j-1] ) // a[i-1] = i-ta litera słowa a |
{ | { | ||
lcs[i][j] = lcs[i-1][j-1]+1; | lcs[i][j] = lcs[i-1][j-1]+1; |
Aktualna wersja na dzień 12:21, 20 mar 2008
#include<iostream> #include<string> using namespace std; string a,b; int lcs[1001][1001]; int main(void) { cin >> a; cin >> b; int n=a.size(), m=b.size(); // n,m <= 1000 // lcs[i][j] : 0 <= i <= n , 0 <= j <= m for (int i=1; i<=n; i++) { for (int j=1; j<=m; j++) { if ( a[i-1] == b[j-1] ) // a[i-1] = i-ta litera słowa a { lcs[i][j] = lcs[i-1][j-1]+1; } else { lcs[i][j] = max( lcs[i-1][j] , lcs[i][j-1] ); } } } cout << lcs[n][m] << endl; return 0; } |
|