[Offer收割]编程练习赛28 register

Ended

Participants:277

Verdict:Accepted
Score:100 / 100
Submitted:2017-09-24 12:42:55

Lang:G++

Edit
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
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
char s_[800000 + 1], s[(800000 + 1) * 2 + 1];
/* number of chars to one side of the middle */
int p[(800000 + 1) * 2 + 1];
int maxr = -1, maxrp;
int main() {
    // scanf("%d", &t);
    scanf("%s", s_);
    int l = strlen(s_);
    memset(s, '#', sizeof(s));
    for (int i = 0; i < l; ++i)
        s[i * 2 + 1] = s_[i];
    long long ans = 0;
    for (int i = 0; i < 2 * l + 1; ++i) {
        if (i <= maxr)
            p[i] = std::min(maxr - i, p[2 * maxrp - i]);
        while (i - p[i] > 0 && i + p[i] < 2 * l && s[i - p[i] - 1] == s[i + p[i] + 1])
            ++p[i];
        if (i + p[i] > maxr) {
            maxr = i + p[i];
            maxrp = i;
        }
        ans += p[i] / 2 + (s[i] == '#' ? 0 : 1);
    }
    cout << ans << endl;
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX