Chương trình tìm tiền tố dài nhất cũng là hậu tố trong C++

Mô tả bài toán

Cho xâu s, tìm tiền tố dài nhất (khác chính xâu) mà cũng là hậu tố của s. Nếu không có trả về rỗng.

Ví dụ: "madam" → "m" (tiền tố "m" và hậu tố "m").

Giải thuật (KMP LPS)

1. Tính mảng lps (longest proper prefix which is also suffix) cho xâu s.
2. lps[n-1] cho độ dài tiền tố/hậu tố dài nhất.
3. Trả về s.substr(0, lps[n-1]).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    vector<int> lps(string s) {
        int n = s.size();
        vector<int> ret(n);
        int j = 0, i = 1;
        while (i < n) {
            if (s[i] == s[j]) { ret[i] = j+1; i++; j++; }
            else if (j > 0) j = ret[j-1];
            else i++;
        }
        return ret;
    }
    string longestPrefix(string s) {
        int n = s.size();
        if (n == 1) return "";
        vector<int> v = lps(s);
        int x = v[n-1];
        return s.substr(0, x);
    }
};

int main() {
    Solution ob;
    cout << ob.longestPrefix("helloworldhello");
    return 0;
}

Đầu vào

"helloworldhello"

Đầu ra

hello