P10170 [DTCPC 2024] 小方和小立方 题解

· · 题解

前言

看别人枚举字串状态，我表示无语，赛时还以为是一道很难的题呢，写了马拉车，调了好久才调出来。我保证我的做法绝对新颖，时间复杂度和空间复杂度都是 O(N)。

思路

看到题目，不难想到马拉车。但是又多了一个条件：

每个字符的出现次数不超过 2。

但这样也很简单，在向外延伸时多判断一个条件即可。

算法详解

算法由来

在求解最长回文子串的问题时，一般的思路是以当前字符为中心，向其左右两边扩展寻找回文，但是这种解法的时间复杂度是 O(N^2)，那么能不能将时间复杂度再降低一点？做到线性？马拉车算法就完美地解决了这个问题。

说人话就是把时间复杂度降低为 O(N)。

预处理

回文字符串以其长度来分，可以分为奇回文（其长度为奇数）、偶回文（其长度为偶数），一般情况下需要分两种情况来寻找回文，马拉车算法为了简化这一步，对原始字符串进行了处理，在每一个字符的左右两边都加上特殊字符（肯定不存在于原字符串中的字符），让字符串变成一个奇回文。例如：

注：X 为特殊字符，以后使用美元符号。

做法

在预处理后，先看是否超出边界 R，如果超出，就直接暴力向外扩展；如果没有，就先借鉴 i 对于 M 的中心点 k 所可以扩展的最长半径，然后再暴力向外扩展。（这里还要向外扩展的原因是，可能 k 在边上，无法向左或向右扩展。）

如果扩展最长半径已经超出边界，就更新边界的值。

最后打擂即可。

注意最后输出的是 ans-1，原因是里面加了特殊符号，导致原来长度变为原先的 2 倍再加 1，而打擂求的是半径，因此直接减 1 即可。

模板

下面给出求最长回文串长度的例题和代码。

题目：P3805 【模板】manacher。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 11000002;
// n 代表一开始字符串的长度
// m 代表添加特殊符号后的字符串的长度
// p[i] 代表往一边能够扩展的字符数即为从 i 开始的最大回文半径 
int n, m, p[N * 2 + 2];
// s[] 代表一开始的字符串
// t[] 代表添加特殊符号后的字符串 
char s[N + 2], t[N * 2 + 3];
// 马拉车 
inline void manacher() {
    n = strlen(s + 1);
    m = 0;
    // 添加特殊符号 
    t[++m] = '$';   
    for(int i = 1; i <= n; i++) {
        t[++m] = s[i]; t[++m] = '$';
    }
    int M = 0, R = 0;
    for(int i = 1; i <= m; i++) {
        // k 是 i 对于 M 的对称点 
        int k = M * 2 - i;
        if(i > R) p[i] = 1;
        else p[i] = min(p[k], R - i + 1);
        // 暴力向外扩展 
        while(i - p[i] > 0 && i + p[i] <= m && t[i - p[i]] == t[i + p[i]])
            ++p[i];
        if(i + p[i] - 1 > R) M = i, R = i + p[i] - 1;
    }
}
int main() {
    // 从 1 开始读入 
    scanf("%s", s + 1);
    manacher();
    int ans = 0;
    for(int i = 1; i <= m; i++) ans = max(ans, p[i]);
    printf("%d", ans - 1);
    return 0;
}

AC 记录：link

小结

小结

马拉车算法将求解最长回文子串的时间复杂度降低到了 O(N)，虽然也牺牲了部分空间，其空间复杂度为 O(N)，但是其算法的巧妙之处还是值得学习和借鉴的。

这道题我感觉还可以枚举形态做，但是用马拉车进行求解复杂度是惊人的 O(N)。

个人认为这种算法应该叫条件马拉车，在朴素马拉车的基础上增加了一个条件。

本题代码

先放 AC 记录啦~

AC 记录：link

#include <bits/stdc++.h>
#define N 50010
using namespace std;
// n 代表一开始字符串的长度
// m 代表添加特殊符号后的字符串的长度
// p[i] 代表往一边能够扩展的字符数即为从 i 开始的最大回文半径 
// cnt[] 代表每个字母出现的次数
int n, m, p[N * 2 + 2], cnt[30];
// s[] 代表一开始的字符串
// t[] 代表添加特殊符号后的字符串 
char s[N + 2], t[N * 2 + 3];
// 马拉车 
inline void manacher() {
    n = strlen(s + 1);
    m = 0;
    // 添加特殊符号 
    t[++m] = '$';
    for(int i = 1; i <= n; i++) {
        t[++m] = s[i];
        t[++m] = '$';
    }
    int M = 0, R = 0;
    for(int i = 1; i <= m; i++) {
        // 每次需要清空数组
        memset(cnt, 0, sizeof(cnt));
        // k 是 i 对于 M 的对称点 
        int k = M * 2 - i;
        if(i > R) {
            p[i] = 1;
            // 本身记一次数
            if(t[i] != '$') {
                cnt[ t[i] - 'a' ] = 1;
            }
        }
        else {
            p[i] = min(p[k], R - i + 1);
            // 将之前的数据搬运过来
            for(int j = i - p[i] + 1; j <= i + p[i] - 1; j++) {
                if(t[j] != '$') cnt[ t[j] - 'a' ]++;
            }
        }
        // 暴力向外扩展，记得多加了一个条件
        while(i - p[i] > 0 && i + p[i] <= m && (t[i - p[i]] == t[i + p[i]])) {
            if(t[i - p[i]] == '$') {
                ++p[i];
            }else {
                // 注意要先判断，再让 p[i] 自增，否则 p[i] 的值会改变
                cnt[ t[i - p[i]] - 'a' ] += 2;
                if(cnt[ t[i - p[i]] - 'a' ] <= 2){
                    ++p[i]; 
                }else break; // 否则就不可以继续延伸了，跳出循环    
            }    
        }   
        // 更新边界
        if(i + p[i] - 1 > R) M = i, R = i + p[i] - 1;
    }
}
int main() {
    // 从 1 开始读入 
    scanf("%s", s + 1);
    manacher();
    int ans = 0;
    for(int i = 1; i <= m; i++) {
        ans += p[i] / 2;
        // 直接除以二下取整得到半径
    }
    printf("%d", ans);
    return 0;
}