Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.9 kB
20
Indexable
Never
#include <bits/stdc++.h>
using namespace std;
int main() {
    // читаем строку
    string s; cin >> s;
    // предподсчёт: для каждого символа находим ближайший справа A и X:
    int n = (int)s.size();
    vector<int> nearestX(n), nearestA(n);
    nearestA[n-1] = n; // ведёт за пределы строки
    nearestX[n-1] = n; // ведёт за пределы строки
    for (int i = n-2; i >= 0; i--) {
        if (s[i+1] == 'X') {
            // следующий символ равен 'X'
            nearestX[i] = i+1; // он становится ближайшим X
            nearestA[i] = nearestA[i+1]; // ближайший A не меняется
        } else {
            // следующий символ равен 'X'
            nearestA[i] = i+1; // он становится ближайшим A
            nearestX[i] = nearestX[i+1]; // ближайший X не меняется
        }
    }
    // теперь мы можем быстро находить следующий X и A. Решаем задачу:
    const string pattern = "AXXAXA";
    const int m = (int)pattern.size();
    int64_t answer = 0;
    for (int i = 0; i < n; i++) {
        // i - начальная позиция. Начиная с неё, ищем "AXXAXA"-вхождение:
        int patternPos = 0, j = i;
        while (patternPos < m && j < n) {
            if (s[j] == pattern[patternPos]) {
                answer += (j+1);
                patternPos++;
                j++;
            } else if (s[j] == 'X') {
                j = nearestA[j]; // переходим к следующему 'A'
            } else {
                j = nearestX[j]; // переходим к следующему 'X'
            }
        }
    }
    cout << answer << endl;
    return 0;
}