Kiểm tra chuỗi lặp lại mẫu con (Repeated Substring Pattern) trong C++

Cho chuỗi không rỗng. Kiểm tra có thể tạo bằng cách lặp lại một substring nhiều lần không.

Input: "abaabaaba" -> true (lặp "aba")

Giải pháp: Dùng mảng KMP (prefix function / LPS). Nếu độ dài chuỗi chia hết cho (n - lps[n-1]) và lps[n-1] > 0 thì true.

Chương trình minh họa

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
    bool repeatedSubstringPattern(string s){
        int n = s.size();
        vector<int> dp(n);
        int i = 1, j = 0;
        while(i < n){
            if(s[i] == s[j]){ dp[i] = j+1; i++; j++; }
            else {
                if(j > 0) j = dp[j-1];
                else { dp[i] = 0; i++; }
            }
        }
        return dp[n-1] && n % (n - dp[n-1]) == 0;
    }
};
int main(){
    Solution ob;
    cout << (ob.repeatedSubstringPattern("abaabaaba") ? "true" : "false");
    return 0;
}

Kết quả

true