Longest Common Subsequence (LCS) (not necessarily consecutive) Simplified. O(mn) time, O(n) space. */
| 218 | Simplified. O(mn) time, O(n) space. |
| 219 | */ |
| 220 | static unsigned lcs(const TokenSeq &X, const TokenSeq &Y, |
| 221 | const unsigned m, const unsigned n) |
| 222 | { |
| 223 | // Here: m,n >= 0. |
| 224 | unsigned L[2][n+1]; // small 2 by n+1 matrix |
| 225 | unsigned bi; // odd(i) |
| 226 | |
| 227 | // 0-th row and 0-th column contains all zeroes: |
| 228 | for (unsigned j = 0; j<=n; j++) // at least once |
| 229 | L[0][j] = 0; |
| 230 | L[1][0] = 0; |
| 231 | |
| 232 | for (unsigned i = 1; i<=m; i++) { // at least once |
| 233 | bi = i & 1; |
| 234 | for (unsigned j = 1; j<=n; j++) // at least once |
| 235 | if (X[i-1] == Y[j-1]) |
| 236 | L[bi][j] = L[1-bi][j-1] + 1; |
| 237 | else |
| 238 | L[bi][j] = max(L[1-bi][j], L[bi][j-1]); |
| 239 | // After seeing i elems: L[bi][n] <= i is actual length; i is upperbound. |
| 240 | // i - L[bi][n] is # different elements; might only get larger (1 per row) |
| 241 | //cerr << "L[" << i << "][n]: " << L[bi][n] << endl; |
| 242 | //if (L[bi][n] >= mincommon) break; |
| 243 | } |
| 244 | /* L[m][n] contains length of LCS for X[0..n-1] and Y[0..m-1] */ |
| 245 | return L[bi][n]; |
| 246 | } |
| 247 | |
| 248 | // An upperbound for the length of an LCS. |
| 249 | static unsigned lcs_upperbound(const TokenBag &t1, const TokenBag &t2) |