1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);

    string s;
    cin >> s;

    long long res = 0;
    vector <vector <bool>> is(3, vector <bool>(s.size()));
    vector <vector <int>> pos(3);
    vector <vector <int>> appeared(3, vector <int>(s.size()+1));

    //ab, ac, bc
    int ab=0, ac=0, bc=0;
    vector <int> cnt (3);
    char prev = 'a' - 1, prevc='a'-1;
    int index=0, previndex=0;

    bool firstchar = 1;
    char first;

    first = s[0];
    index = first - 'a';
    is[index][0] = 1;
    pos[index].push_back(0);
    appeared[0][1] = (first == 'a');
    appeared[1][1] = (first == 'b');
    appeared[2][1] = (first == 'c');
    cnt[index]++;
    res++;
    prev = first;
    prevc = first;
    previndex = index;

    for (int i = 1; i < s.size(); i++) {
        char c;
        c = s[i];

        if (firstchar) {
            if (c == first) {
                is[index][i] = 1;
                pos[index].push_back(i);
                appeared[0][i+1] = appeared[0][i] + (c == 'a');
                appeared[1][i+1] = appeared[1][i] + (c == 'b');
                appeared[2][i+1] = appeared[2][i] + (c == 'c');
                cnt[index]++;

                res += cnt[index];
            }
            else {
                firstchar = 0;
                i--;

                switch (first) {
                case 'a':
                    ab += cnt[index];
                    ac += cnt[index];
                    break;
                case 'b':
                    ab += cnt[index];
                    bc += cnt[index];
                    break;
                case 'c':
                    ac += cnt[index];
                    bc += cnt[index];
                    break;                
                }

            }
        }
        else {
            if (c != prev) {
                previndex = index;
            }
            index = c - 'a';

            is[index][i] = 1;
            pos[index].push_back(i);

            appeared[0][i+1] = appeared[0][i] + (c == 'a');
            appeared[1][i+1] = appeared[1][i] + (c == 'b');
            appeared[2][i+1] = appeared[2][i] + (c == 'c');

            switch (c) {
            case 'a':
                ab++;
                ac++;
                bc = 0;
                break;
            case 'b':
                ab++;
                bc++;
                ac = 0;
                break;
            case 'c':
                ac++;
                bc++;
                ab = 0;
                break;
            }

            //pojedyncze slowa
            if (c == prev) {
                cnt[index]++;
                res += cnt[index];
            }
            else {
                prevc = prev;
                prev = c;

                cnt[0] = 0;
                cnt[1] = 0;
                cnt[2] = 0;
                cnt[index]++;
                res++;

            }

            //podwojne
            string two;
            two.push_back(min(c, prevc));
            two.push_back(max(c, prevc));
            int base;
            if (two == "ab") {
                base = ab;
            }
            else if (two == "ac") {
                base = ac;
            }
            else /*two==bc*/ {
                base = bc;
            }

            for (int j = cnt[index]; pos[index].size() >= j && pos[previndex].size() >= j && (j <= base / 2); j++) {
                int pos2 = min(pos[index][pos[index].size() - j], pos[previndex][pos[previndex].size() - j]);

                if (appeared[index][i+1] - appeared[index][pos2] == appeared[previndex][i+1] - appeared[previndex][pos2])
                    res++;
            }

            //potrojne
            for (int j = cnt[index]; ((pos[0].size() >=j) && (pos[1].size() >= j) && (pos[2].size()>= j) && (j <= (i+1)/3)); j++) {
                int pos2 = min (min(pos[0][pos[0].size() - j], pos[1][pos[1].size() - j]), pos[2][pos[2].size() - j]);

                if (appeared[0][i+1] - appeared[0][pos2] == appeared[1][i+1] - appeared[1][pos2] &&
                    appeared[0][i+1] - appeared[0][pos2] == appeared[2][i+1] - appeared[2][pos2])
                    res++;
            }
        }
    }

    cout << res << "\n";
}