Celery's Blog

0%

LeetCode-Day55

发表于 Valine：

Manacher

https://www.cnblogs.com/fan1-happy/p/11166182.html

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
int f[N << 1];
char str[N << 1];
LL Manacher(char *s) {
    int n = strlen(s + 1);
    int maxLen = -1;    // 记录最大长度
    str[1] = '#';
    for(int i = 1; i <= n; i++) {
        str[i << 1] = s[i];
        str[i << 1 | 1] = '#';
    }
    n = n << 1 | 1;
    str[0] = '$';
    str[n + 1] = '*';
    // mx 表示以id为中心的最长回文右边界，即mx = id + p[id]
    int id = 1, mx = 1;
    LL ret = 0;
    for(int i = 1; i <= n; i++) {
        // 若 i < mx, 则用mx和j来更新到已知的可以更新的最大长度
        // 2 * id - i表示的是i关于id的对称点j，而f[j]表示以j为中心的最长回文半径
        f[i] = min(f[id * 2 - i], mx - i);
        while(str[i - f[i]] == str[i + f[i]]) {
            f[i]++;
        }
        if(i + f[i] > mx) {
            mx = i + f[i];
            id = i;
        }
        maxLen = max(maxLen, f[i] - 1);
        ret += f[i] >> 1;
    }
    cout << "maxLen = " << maxLen << endl;
    return ret;
}

Ps：这个数组s是从1开始计数的，因此aca会变成$#a#c#a#

Hdu 3613 Best Reward

给出26个字母对应的价值。现要将一个字符串分成两截。一段字符串若是回文串则其价值为所有字母价值和，否则为0。问分割后的两串价值和最大是多少。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 500005;
int value[30];
char s[N];
char str[N << 1];
int f[N << 1];
int pre[N];
int p[N];

void Manacher() {
    memset(f, 0, sizeof(f));
    int n = strlen(s + 1);
    int len = strlen(s);
    int maxLen = 
    str[1] = '#';
    for(int i = 1; i <= n; i++) {
        str[i << 1] = s[i];
        str[i << 1 | 1] = '#';
    }
    n = n << 1 | 1;
    str[0] = '$'; str[n + 1] = '*';
    int id = 1, mx = 1;
    for(int i = 1; i <= n; i++) {
        f[i] = min(f[id*2-i], mx-i);
        while(str[i - f[i]] == str[i + f[i]]) {
            f[i]++;
        }
        if(i + f[i] > mx) {
            id = i;
            mx = i + f[i];
        }
    }
    memset(pre, 0, sizeof(pre));
    for(int i = 1; i < len; i++) {
        pre[i] = pre[i - 1] + value[s[i] - 'a'];
    }
    int maxSum = 0;
    len -= 1;
    for(int i = 3; i < n; i += 2) {
        int sum = 0;
        if(f[(i+1) >> 1] * 2 - 1 == i) {
            sum += pre[(i - 1) >> 1];
        }
        if(f[(i + n) >> 1] * 2 - 1 == n - i + 1) {
            sum += (pre[len] - pre[(i - 1) >> 1]);
        }
        maxSum = max(maxSum, sum);
    }
    printf("%d\n", maxSum);
}

int main() {
    int n;
    scanf("%d", &n);
    while(n--) {
        for(int i = 0; i < 26; i++) {
            scanf("%d", &value[i]);
        }
        scanf("%s", &s);
        for(int i = strlen(s); i >= 0; i--) {
            s[i + 1] = s[i];
        }
        Manacher();
    }
}