798236606 发表于 2020-2-27 19:07:43

PTA A_1040 Longest Symmetric String

本帖最后由 798236606 于 2020-8-29 11:18 编辑

传送门：https://pintia.cn/problem-sets/9 ... /994805446102073344

解：
manacher算法
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int maxn = 1e3 + 10;

char a;
char b;
int p;

int init(char *a)
{

    b = '!';
    b = '#';

    int j = 2;

    for (int i = 0; i < strlen(a); ++i)
    {
      b = a;
      b = '#';
    }
    b = '\0';

    return j;
}

int manacher(char *a)
{
    int len = init(a);
    int id = -1, mx = 0, ans = -1;

    for (int i = 1; i < len; ++i)
    {
      p = (i < mx) ? min(p, mx - i) : 1;
   
      while (b] == b]) ++p;

      if (i + p > mx)
      {
            mx = i + p;
            id = i;
      }

      if (p > ans) ans = p;
    }

    return ans - 1;
}

int main(void)
{
    // freopen("input.txt", "r", stdin);
    scanf("%[^\n]", a);

    printf("%d", manacher(a));

    return 0;
}
页: [1]
查看完整版本: PTA A_1040 Longest Symmetric String