元音回文

问题描述

现在有一个长度为 $n$ 的字符串，都有小写字母组成。
现在所有元音字母都可以看作相同的字符
输出最长回文子串的长度

一个与自身的逆序相同的字符串即为回文串
比如 $aba,aabbaa,asdffdsa$ 都为回文串

输入格式

第一行一个整数 $n$ , $1\le n\le5000$，表示字符串长度
接下来一行表示字符串

输出格式

输出一行，一个数，代表答案

样例输入

10
aeioubaeio

样例输出

9

样例解释

所以元音都可以看作相同字符，所以回文串为 $eioubaeio$

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

char c;
int n;
int ans = 0;

char s[50005], str[50005];
int RL[50005];

int Manacher() {
    int len = n;
    *s = '#';
    for (int i = 0; i < len; i++) {
        s[(i << 1) + 1] = str[i];
        s[(i << 1) + 2] = '#';
    }
    len = (len << 1) + 1;
    int max = 1, pos=0, maxRight = -1;
    memset(RL, 0, sizeof(RL));
    for (int i = 0; i < len; i++) {
        if (i < maxRight)
            RL[i] = std::min(RL[(pos << 1) - i], maxRight - i);
        else
            RL[i] = 1;
        while (i - RL[i] >= 0 && i + RL[i] < len && s[i - RL[i]] == s[i + RL[i]])
            ++RL[i];
        if (i + RL[i] > maxRight) {
            pos = i;
            maxRight = i + RL[i];
        }
        max = std::max(max, RL[i] - 1);
    }
    return max;
}

inline bool yuan(const char& c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) {
        scanf(" %c", &str[i]);
        if(yuan(str[i]))
            str[i] = '.';
    }
    cout<<Manacher();
    return 0;
}