Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- int longestSubsequenceEfficient(std::string x, std::string y) {
- int m = x.length();
- int n = y.length();
- int result = 0;
- // For each starting position in y
- for (int i = 0; i < n; i++) {
- // Early termination if remaining length can't beat current max
- if (n - i <= result) break;
- // Use a sliding window approach with two pointers
- std::vector<std::vector<int>> next(n + 1, std::vector<int>(26, -1));
- // Precompute next occurrence of each character
- for (int j = n - 1; j >= i; j--) {
- for (int c = 0; c < 26; c++) {
- next[j][c] = next[j + 1][c];
- }
- next[j][y[j] - 'a'] = j;
- }
- // Try to match each substring starting at position i
- for (int len = 1; i + len - 1 < n; len++) {
- bool isSubsequence = true;
- int pos = 0;
- // Check if y[i...i+len-1] is a subsequence of x
- for (int j = i; j < i + len; j++) {
- // Find the next occurrence of y[j] in x starting from pos
- while (pos < m && x[pos] != y[j]) {
- pos++;
- }
- if (pos >= m) {
- isSubsequence = false;
- break;
- }
- pos++; // Move to the next position in x
- }
- if (isSubsequence) {
- result = std::max(result, len);
- } else {
- // If current length is not a subsequence, longer ones won't be either
- break;
- }
- }
- }
- return result;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
