#include <iostream>
#include <vector>
#include <string>
using namespace std;

class KMP {
private:
    string pattern;
    vector<int> pi; // 失配函数
    
public:
    KMP(const string& p) : pattern(p) {
        computePi();
    }
    
    // 构建失配函数
    void computePi() {
        int m = pattern.length();
        pi.assign(m, 0);
        
        for (int i = 1; i < m; i++) {
            int j = pi[i - 1];
            
            // 寻找最长相等前后缀
            while (j > 0 && pattern[i] != pattern[j]) {
                j = pi[j - 1];
            }
            
            if (pattern[i] == pattern[j]) {
                j++;
            }
            
            pi[i] = j;
        }
    }
    
    // 在文本中查找所有匹配位置
    vector<int> findAll(const string& text) {
        vector<int> matches;
        int n = text.length();
        int m = pattern.length();
        
        if (m == 0) return matches;
        
        int j = 0; // pattern的索引
        
        for (int i = 0; i < n; i++) {
            // 利用失配函数跳过不必要的比较
            while (j > 0 && text[i] != pattern[j]) {
                j = pi[j - 1];
            }
            
            if (text[i] == pattern[j]) {
                j++;
            }
            
            // 找到完整匹配
            if (j == m) {
                matches.push_back(i - m + 1);
                j = pi[j - 1]; // 继续寻找下一个匹配
            }
        }
        
        return matches;
    }
    
    // 获取失配函数数组
    vector<int> getPi() const {
        return pi;
    }
    
    // 显示失配函数的构建过程
    void showPiConstruction() {
        cout << "模式串: " << pattern << endl;
        cout << "索引:   ";
        for (int i = 0; i < pattern.length(); i++) {
            cout << i << " ";
        }
        cout << endl;
        cout << "π函数:  ";
        for (int x : pi) {
            cout << x << " ";
        }
        cout << endl;
    }
};

int main() {
    string text = "ABABDABACDABABCABCABCABABABCAC";
    string pattern = "ABABCAC";
    
    cout << "文本: " << text << endl;
    cout << "模式: " << pattern << endl << endl;
    
    KMP kmp(pattern);
    kmp.showPiConstruction();
    
    vector<int> matches = kmp.findAll(text);
    
    cout << "\n匹配位置: ";
    for (int pos : matches) {
        cout << pos << " ";
    }
    cout << endl;
    
    // 显示匹配的子串
    cout << "\n匹配详情:" << endl;
    for (int pos : matches) {
        cout << "位置 " << pos << ": " << text.substr(pos, pattern.length()) << endl;
    }
    
    return 0;
}

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

class ZAlgorithm {
public:
    // 计算Z数组
    static vector<int> computeZ(const string& s) {
        int n = s.length();
        vector<int> z(n);
        z[0] = n; // z[0]定义为字符串长度
        
        int l = 0, r = 0; // Z-box的左右边界
        
        for (int i = 1; i < n; i++) {
            if (i <= r) {
                // i在Z-box内，可以利用之前的信息
                z[i] = min(r - i + 1, z[i - l]);
            }
            
            // 尝试扩展匹配
            while (i + z[i] < n && s[z[i]] == s[i + z[i]]) {
                z[i]++;
            }
            
            // 更新Z-box
            if (i + z[i] - 1 > r) {
                l = i;
                r = i + z[i] - 1;
            }
        }
        
        return z;
    }
    
    // 使用Z算法进行字符串匹配
    static vector<int> stringMatch(const string& text, const string& pattern) {
        string combined = pattern + "#" + text; // 用特殊字符分隔
        vector<int> z = computeZ(combined);
        
        vector<int> matches;
        int patternLen = pattern.length();
        
        for (int i = patternLen + 1; i < combined.length(); i++) {
            if (z[i] == patternLen) {
                matches.push_back(i - patternLen - 1);
            }
        }
        
        return matches;
    }
    
    // 找所有回文子串
    static vector<pair<int, int>> findPalindromes(const string& s) {
        vector<pair<int, int>> palindromes;
        int n = s.length();
        
        // 检查奇数长度回文
        for (int center = 0; center < n; center++) {
            string left = s.substr(0, center + 1);
            reverse(left.begin(), left.end());
            string right = s.substr(center);
            
            string combined = left + "#" + right;
            vector<int> z = computeZ(combined);
            
            for (int i = left.length() + 1; i < combined.length(); i++) {
                int len = z[i];
                if (len > 0 && center - len + 1 >= 0 && center + len - 1 < n) {
                    palindromes.push_back({center - len + 1, center + len - 1});
                }
            }
        }
        
        return palindromes;
    }
};

int main() {
    string text = "AABAACAADAABAABA";
    string pattern = "AABA";
    
    cout << "文本: " << text << endl;
    cout << "模式: " << pattern << endl;
    
    // 计算模式串的Z数组
    vector<int> z = ZAlgorithm::computeZ(pattern);
    cout << "\n模式串的Z数组: ";
    for (int x : z) cout << x << " ";
    cout << endl;
    
    // 查找匹配
    vector<int> matches = ZAlgorithm::stringMatch(text, pattern);
    cout << "\n匹配位置: ";
    for (int pos : matches) {
        cout << pos << " ";
    }
    cout << endl;
    
    // 显示匹配的子串
    cout << "\n匹配的子串:" << endl;
    for (int pos : matches) {
        cout << "位置 " << pos << ": " << text.substr(pos, pattern.length()) << endl;
    }
    
    return 0;
}