Manacher模板 54pts 求调!
查看原帖
Manacher模板 54pts 求调!
519573
Daniel_yao楼主2024/7/18 20:33
#include<bits/stdc++.h>
#define int long long
#define For(i,l,r) for(int i=l;i<=r;++i)
#define FOR(i,r,l) for(int i=r;i>=l;--i)

using namespace std;

const int N = 4e7; 

int n, d[N];

char s[N];

string t = " ";

int Manacher() {
  int ans = 0;
  for (int i = 1, l = 1, r = 0; i <= n; i++) {
    int k = (i > r ? 1 : min(d[l + r - i], r - i + 1));
    while(i - k >= 1 && i + k <= n && t[i - k] == t[i + k]) k++;
    d[i] = --k;
    if(r < i + k) {
      r = i + k;
      l = i - k;
    }
  }
  For(i,1,n) {
    if(t[i] == '#') {
      ans = max(ans, d[i] - 1);
    } else {
      ans = max(ans, d[i]);
    }
  }
  return ans;
}

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> (s + 1);
  n = strlen(s + 1);
  For(i,1,n) {
    t += "#", t += s[i];
  }
  t += '#';
  n = 2 * n + 1;
  cout << Manacher() << '\n';
  return 0;
}
2024/7/18 20:33
加载中...