抽象玄学RE求助
查看原帖
抽象玄学RE求助
566168
川寰boy楼主2023/8/5 20:57
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <stack>
#include <deque>

using namespace std;

#define rd read()
#define wt(a) write(a)

#define int long long

const int N = 1e7 + 1e6 + 10;
const int MOD = 998244353;
const int INF = 0x7fffffff;
const int FillINF = 0x3f3f3f3f;

void write(int n)
{
    if (n < 0)
    {
        putchar('-');
        n = -n;
    }
    if (n < 10)
    {
        putchar(n + '0');
        return;
    }
    write(n / 10);
    putchar(n % 10 + '0');
    return;
}

int read()
{
    char ch;
    int type = 1, n = 0;
    ch = getchar();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
        {
            type = -1;
        }
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        n = (n << 1) + (n << 3) + (ch ^ 48);
        ch = getchar();
    }
    return n * type;
}

int n, mr, mid;
int p[N];

char temp[N];
char s[N];

void init()
{
    int i;
    // s = "";
    s[0] = '~';
    // s += '~';
    s[1] = '#';
    // s += '#';
    int t = strlen(temp);
    for (i = 1; i <= t; i++)
    {
        s[i * 2] = temp[i - 1];
        s[(i * 2) + 1] = '#';
        // s += temp[i];
        // s += '#';
        // s[i * 2] = temp[i];
        // s[i * 2 + 1] = '#';
    }
    // cout << i * 2 << '\n';
    s[i * 2] = '^';
    // s += '^';
    // cout << s << '\n';
    return ;
}

int Manacher()
{
    int i, j;
    int t = (strlen(temp));
    int len = (t + 1) * 2;
    int ans = -1;
    mid = mr = 1;
    for (i = 1; i < len; i++)
    {
        if (i < mr)
        {
            p[i] = min(p[mid * 2 - i], mr - i);
        }
        else
        {
            p[i] = 1;
        }
        while (s[i - p[i]] == s[i + p[i]])
        {
            p[i]++;
        }
        if (i > mr - p[i])
        {
            mid = i;
            mr = i + p[i];
        }
        ans = max(ans, p[i] - 1);
    }
    return ans;
}

signed main()
{
    int T;
    int i, j;
    T = 1;
    while (T--)
    {
        cin >> temp;
        // scanf("%s", temp);
        // cin >> temp;
        init();
        cout << Manacher();
        if (T != 1)
        {
            putchar('\n');
        }
    }
    return 0;
}

init函数中for循环如果写成i <= t就会RE,写成i <= strlen(temp) 就不RE,会TLE。

2023/8/5 20:57
加载中...