Алгоритм Манакера

vector<int> oddPalindromeCount(string &s) {
    vector<int> palindromeCount(s.size(), 1);
    int l, r = -1;

    for (int i = 0; i < s.size(); i++) {
        int &p = palindromeCount[i];
        if (i <= r)
            p = min(palindromeCount[l + r - i], r - i);

        while (0 <= i - p && i + p < s.size() && s[i - p] == s[i + p])
            p++;

        if (i + p - 1 > r) {
            l = i - p + 1;
            r = i + p - 1;
        }
    }

    return palindromeCount;
}

vector<vector<int>> manacher(string &s) {
    string t = "#";
    for (char c : s) {
        t += c;
        t += '#';
    }

    vector<int> palindromeCount = oddPalindromeCount(t);

    vector<vector<int>> res(2);
    for (int i = 0; i + 1 < palindromeCount.size(); i++)
        res[i % 2].push_back(palindromeCount[i] / 2);
    return res;
}

vector<int> evenPalindromeCount(string &s) {
    vector<int> palindromeCount(s.size());
    int l, r = -1;

    for (int i = 0; i < s.size(); i++) {
        int &p = palindromeCount[i];
        if (i <= r)
            p = min(palindromeCount[l + r - i + 1], r - i + 1);

        while (0 <= i - p - 1 && i + p < s.size() && s[i - p - 1] == s[i + p])
            p++;

        if (i + p - 1 > r) {
            l = i - p;
            r = i + p - 1;
        }
    }

    return palindromeCount;
}

Алгоритм Манакера

Навигация

Поиск