HA35

#include <iostream>
#include <vector>
#include <string>

class KMP {
public:
    KMP(const std::string& pattern) : pattern(pattern) {
        FindMaxBorder();
    }

    std::vector<int> search(const std::string& text) {
        std::vector<int> result;
        int m = pattern.size();
        int n = text.size();
        int i = 0;
        int j = 0;

        while (i < n) {
            if (pattern[j] == text[i]) {
                j++;
                i++;
            }
            if (j == m) {
                result.push_back(i - j);
                j = maxborder[j - 1];
            } else if (i < n && pattern[j] != text[i]) {
                if (j != 0) {
                    j = maxborder[j - 1];
                } else {
                    i++;
                }
            }
        }
        return result;
    }

    std::vector<int> find_prefix() {
        return maxborder;
    }

private:
    std::string pattern;
    std::vector<int> maxborder;

    void FindMaxBorder() {
        int m = pattern.size();
        maxborder.resize(m);
        int len = 0;
        maxborder[0] = 0;
        int i = 1;

        while (i < m) {
            if (pattern[i] == pattern[len]) {
                len++;
                maxborder[i] = len;
                i++;
            } else {
                if (len != 0) {
                    len = maxborder[len - 1];
                } else {
                    maxborder[i] = 0;
                    i++;
                }
            }
        }
    }
};

int main() {
    std::string text = "ababcabcabababd";
    std::string pattern = "ababd";
    KMP kmp(pattern);
    std::vector<int> result = kmp.search(text);

    std::cout << "Паттерн найден по индексу: ";
    for (int index : result) {
        std::cout << index << " ";
    }
    std::cout << std::endl;

    std::vector<int> prefix = kmp.find_prefix();
    std::cout << "Массив префиксов: ";
    for (int p : prefix) {
        std::cout << p << " ";
    }
    std::cout << std::endl;

    return 0;
}