题目链接

LuoguP4555

题目概括

给定一个字符串 $s$,求出其最长双回文子串。

数据范围 $2\leq |s| \leq 10^5$

思路要点

考虑这个双回文子串的端点位置。

用 $Manacher$ 扩展 $rad$ 数组的同时更新每一个结束点的最长距离,和每一个起点的最长距离。

时间复杂度 $\mathcal O(n)$

代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef unsigned long long ull;

namespace Manacher {
int manacher(string t) {
  string s = "~#"; 
  for (int i = 0; i < (int)t.length(); i++) {
    s += t[i];
    s += '#';
  }
  vector<int> rad(s.length()), a(s.length()), b(s.length());
  int mid = 0, right = 0;
  for (int i = 1; i < (int)s.length(); i++) {
    rad[i] = (i < right ? min(rad[mid * 2 - i], right - i) : 1);
    while (s[i + rad[i]] == s[i - rad[i]]) {
      a[i - rad[i]] = max(a[i - rad[i]], rad[i] - 1);
      b[i + rad[i]] = max(b[i + rad[i]], rad[i] - 1);
      rad[i]++;
    }
    a[i - rad[i]] = max(a[i - rad[i]], rad[i] - 1);
    b[i + rad[i]] = max(b[i + rad[i]], rad[i] - 1);
    if (i + rad[i] > right) {
      right = i + rad[i];
      mid = i;
    }
  }
  int ans = 0;
  // for (int i = 0; i < (int)a.size(); i++) {
  //   cout << a[i] << ' ';
  // } cout << '\n';
  // for (int i = 0; i < (int)b.size(); i++) {
  //   cout << b[i] << ' ';
  // } cout << '\n';
  for (int i = 2; i < (int)s.length() - 1; i++) { 
    ans = max(ans, a[i - 1] + b[i + 1]);
  }
  return ans;
}

int solve(char* s) {
  string t = s;
  return manacher(t);
}

int solve(string s) {
  return manacher(s);
}

}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
  freopen("output.out", "w", stdout);
#endif
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);

  string s;
  cin >> s;
  cout << Manacher::solve(s) << '\n';
  return 0;
}
最后修改:2020 年 03 月 28 日 08 : 44 PM
如果觉得我的文章对你有用,请随意赞赏