Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <bits/stdc++.h>
using namespace std;
const char DUMMY = '.';

int manacher(string s) {
    int n = s.size() * 2 - 1;
    vector <int> f = vector <int>(n, 0);
    string a = string(n, DUMMY);
    for (int i = 0; i < n; i += 2) a[i] = s[i / 2];

    int l = 0, r = -1, center, res = 0;
    for (int i = 0, j = 0; i < n; i++) {
        j = (i > r ? 0 : min(f[l + r - i], r - i)) + 1;
        while (i - j >= 0 && i + j < n && a[i - j] == a[i + j]) j++;
        f[i] = --j;
        if (i + j > r) {
            r = i + j;
            l = i - j;
        }

        int len = (f[i] + i % 2) / 2 * 2 + 1 - i % 2;
        if (len > res) {
            res = len;
            center = i;
        }
    }

    return res;
}


int main() {
    int n;
    char s[100100];
    scanf("%d%s", &n, s);
    cout << manacher(string(s, n)) << endl;
}

Code mẫu của happyboy99x

#include<cstdio>

typedef long long LL;
#define MOD 1000000007LL
#define N 50000
int n; char s[N+2];
LL h[N+1], pow[N+1], rh[N+1];

inline int hash(int i, int j) {
    return (h[j] - h[i-1] * pow[j-i+1] + MOD * MOD) % MOD;
}

inline int rhash(int i, int j) {
    return (rh[n-i+1] - rh[n-j] * pow[j-i+1] + MOD * MOD) % MOD;
}

void init() {
    pow[0] = 1; h[0] = rh[0] = 0;
    for(int i = 1; i <= n; ++i) {
        h[i] = (h[i-1] * 95 + s[i] - 32) % MOD;
        rh[i] = (rh[i-1] * 95 + s[n-i+1] - 32) % MOD;
        pow[i] = pow[i-1] * 95 % MOD;
    }
}

bool checkLength(int len) {
    for(int i = 1; i + len - 1 <= n; ++i)
        if(hash(i, i + len - 1) == rhash(i, i + len - 1)) return 1;
    return 0;
}

int main() {
    scanf("%d%s", &n, s+1); init();
    int lo = 1, hi = n - (n % 2 == 0); 
    while(lo < hi) {
        int mid = (lo+hi)/2; if(mid % 2 == 0) ++mid;
        if(checkLength(mid)) lo = mid; else hi = mid - 2;
    }
    int res = lo;
    lo = 0; hi = n - n % 2;
    while(lo < hi) {
        int mid = (lo+hi)/2; if(mid % 2) ++mid;
        if(checkLength(mid)) lo = mid; else hi = mid - 2;
    }
    if(lo > res) res = lo;
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <cstdio>
#include <iostream>
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define long long long

const int N = 50005;
const int MOD = 1000000007;
const long MM = (long)MOD * MOD;

using namespace std;

long H[N], R[N], power[N];
char s[N];
int n;

int getHash(int i, int j)
    { return (H[j] - H[i - 1] * power[j - i + 1] + MM) % MOD; }
int getRash(int i, int j)
    { return (R[i] - R[j + 1] * power[j - i + 1] + MM) % MOD; }
bool isPalin(int i, int j)
    { return getHash(i, j) == getRash(i, j); }

int main() {
    #ifdef _LAD_
        freopen("PALINY.in", "r", stdin);
    #endif // _LAD_
    scanf("%d\n%s", &n, s + 1);
    REP(i, 1, n) H[i] = (H[i - 1] * 26 + s[i] - 'a') % MOD;
    REPD(i, n, 1) R[i] = (R[i + 1] * 26 + s[i] - 'a') % MOD;
    power[0] = 1;
    REP(i, 1, n) power[i] = power[i - 1] * 26 % MOD;
    int ans = 0;
    REP(i, 1, n) {
        // even palindrome
        int l = 0, r = min(i, n - i);
        while (l <= r) {
            int mid = l + r >> 1;
            if (isPalin(i - mid + 1, i + mid))
                ans = max(ans, mid << 1), l = mid + 1;
            else
                r = mid - 1;
        }
        // odd palindrome
        l = 0, r = min(i - 1, n - i);
        while (l <= r) {
            int mid = l + r >> 1;
            if (isPalin(i - mid, i + mid))
                ans = max(ans, mid << 1 | 1), l = mid + 1;
            else
                r = mid - 1;
        }
    }
    printf("%d\n", ans);
    return 0;
}

Code mẫu của RR

//Written by RR

{$MODE OBJFPC}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       50111;
  nkey          =       2;
  hkey          :       array[1..nkey] of longint=(
30011,30013);

var
  f1,f2         :       text;
  n,res         :       longint;
  a             :       array[1..MAXN] of longint;
  lt            :       array[1..nkey,0..MAXN] of longint;
  sum           :       array[1..nkey,0..1,0..MAXN] of longint;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    var
      i:longint;
      c:char;
    begin
      readln(f1,n);
      for i:=1 to n do
        begin
          read(f1,c);
          a[i]:=ord(c)-ord('a');
        end;
    end;

procedure init;
    var
      now,hashkey,i:longint;
    begin
      for now:=1 to nkey do
        begin
          hashkey:=hkey[now];
          lt[now,0]:=1;
          for i:=1 to n do
            lt[now,i]:=(lt[now,i-1]*26) mod hashkey;

          for i:=1 to n do
            sum[now,0,i]:=(sum[now,0,i-1]+lt[now,i-1]*a[i]) mod hashkey;
          for i:=n downto 1 do
            sum[now,1,i]:=(sum[now,1,i+1]+lt[now,n-i]*a[i]) mod hashkey;
        end;
    end;

function check(val:longint):boolean;
    var
      i,j,l1,l2,now:longint;
      ok:boolean;
    begin
      for i:=1 to n-val+1 do
        begin
          j:=i+val-1;
          l1:=i-1; l2:=n-j;
          if l1=l2 then begin l1:=0; l2:=0; end
          else if l1>l2 then begin l2:=l1-l2; l1:=0; end
          else begin l1:=l2-l1; l2:=0; end;

          ok:=true;
          for now:=1 to nkey do
            if (lt[now,l1]*(sum[now,0,j]-sum[now,0,i-1]+hkey[now])) mod hkey[now]
             <>(lt[now,l2]*(sum[now,1,i]-sum[now,1,j+1]+hkey[now])) mod hkey[now]
            then ok:=false;
          if ok then exit(true);
        end;
      exit(false);
    end;

function chan:longint;
    var
      l,r,mid,res:longint;
    begin
      l:=1; r:=n shr 1; res:=0;
      while l<=r do
        begin
          mid:=(l+r) shr 1;
          if check(mid shl 1) then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res shl 1);
    end;

function le:longint;
    var
      l,r,mid,res:longint;
    begin
      l:=0; r:=n shr 1; res:=0;
      while l<=r do
        begin
          mid:=(l+r) shr 1;
          if check(mid shl 1+1) then
            begin
              res:=mid;
              l:=mid+1;
            end
          else r:=mid-1;
        end;
      exit(res shl 1+1);
    end;

begin
  openF;
  inp;
  init;
  writeln(f2,max(chan,le));
  closeF;
end.

Code mẫu của hieult

#include <iostream>
#include <vector>
//#include <conio.h>
#include <algorithm>

using namespace std;

int fastFindPalindrome(string &str)
{

     int strLength = str.length();
     vector<int> vec;
     int i = 0;
     int palLength = 0;
     int Longest = 0;
     while(i<strLength)
     {
     if((i > palLength) && (str[i - palLength - 1] == str[i]) )
     {
          palLength += 2;
          i += 1;
          continue;
     }

     vec.push_back(palLength);
     Longest = max (Longest, palLength);

     int s = vec.size() -2;
     int e = s - palLength;

     bool found = false;
     for(int j = s; j > e; j--)
     {
          int d = j -e -1;
          if(vec[j]==d)
          {
               palLength = d;
               found = true;
               break;
          }
          vec.push_back(min(d, vec[j]));
          Longest = max (Longest, min (d, vec[j]));
     }
     if(!found)
     {
          i+=1;
          palLength = 1;
     }
     }
vec.push_back(palLength);
Longest = max (Longest, palLength);

return Longest;
}

int main()
{
    string s;
    int n;
    cin >> n;
    cin >> s;
    cout << fastFindPalindrome(s);
    //getch();
}

Code mẫu của ll931110

program PALINY;
uses math;
const
  input  = '';
  output = '';
  maxn = 50000;
var
  a: array[0..maxn] of char;
  rad: array[0..maxn] of longint;
  res,n: longint;

procedure init;
var
  f: text;
  i: longint;
begin
  assign(f, input);
    reset(f);

  readln(f, n);
  for i := 0 to n - 1 do read(f, a[i]);

  close(f);
end;

procedure solve;
var
  i,j,k: longint;
begin
  res := 0;

  i := 0;
  j := 0;
  while i < n do
    begin
      while (i >= j) and (i + 1 + j < n) and (a[i - j] = a[i + 1 + j]) do inc(j);
      rad[i] := j;

      k := 1;
      while (i >= k) and (i + k < n) and (k <= rad[i]) and (rad[i - k] <> rad[i] - k) do
        begin
          rad[i + k] := min(rad[i - k],rad[i] - k);
          inc(k);
        end;

      j := max(j - k,0);
      i := i + k;
    end;

  for i := 0 to n - 1 do if res < rad[i] * 2 then res := rad[i] * 2;

  i := 0;
  j := 0;
  while i < n do
    begin
      while (i >= j) and (i + 2 + j < n) and (a[i - j] = a[i + 2 + j]) do inc(j);
      rad[i] := j;

      k := 1;
      while (i >= k) and (i + k < n) and (k <= rad[i]) and (rad[i - k] <> rad[i] - k) do
        begin
          rad[i + k] := min(rad[i - k],rad[i] - k);
          inc(k);
        end;

      j := max(j - k,0);
      i := i + k;
    end;

  for i := 0 to n - 1 do if res < rad[i] * 2 + 1 then res := rad[i] * 2 + 1;
end;

procedure printresult;
var
  f: text;
begin
  assign(f, output);
    rewrite(f);
    writeln(f, res);
  close(f);
end;

begin
  init;
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
using namespace std;
string s;
int manacher(const string &s) { 
    string t="^";   
    int c,r;    
    FORE(it,s) {
        assert(*it!='^' && *it!='#' && *it!='$');
        t.push_back('#');
        t.push_back(*it);
    }
    t+="#$";
    int n=t.size(); 
    vector<int> p=vector<int>(n+7,0);
    c=0;
    r=0;
    FOR(i,1,n-1) {
        if (r>i) p[i]=min(r-i,p[2*c-i]);
        else p[i]=0;
        while (t[i+1+p[i]]==t[i-1-p[i]]) p[i]++;
        if (i+p[i]>r) {
            c=i;
            r=i+p[i];
        }       
    }
    int ret=0;
    FOR(i,1,n-1) ret=max(ret,p[i]);
    return (ret);
}
int main(void) {
    srand(time(NULL));
    ios::sync_with_stdio(rand()%2);
    cin >> s >> s;
    cout << manacher(s);
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

int MOD = 7999993;
int COSO = 241;

int n;
char a[120000];
int total[120000], pow[120000];

int POW(int a, int sm) {
    if(sm==0) return 1;
    int r = POW(a,sm/2);
    if(sm%2) return r * 1LL * r % MOD * a % MOD;
    else return r * 1LL * r % MOD;
}

int calc(int i, int j) {
    return (MOD + total[j] - (i==0 ? 0 : total[i-1])) % MOD * 1LL * pow[i] % MOD;
}

int main() {
    scanf("%d", &n);
    gets(a);
    gets(a);
    memmove( a + n, a, n);
    reverse( a, a + n);
    for(int i=0,z=1;i<2*n;++i,z = ( z * COSO ) % MOD) 
        total[i] = ((i==0 ? 0 : total[i-1]) + z * a[i]) % MOD;
    for(int i=0,z=POW(COSO,MOD-2);i<2*n;++i)
        pow[i] = (i==0 ? 1 : (pow[i-1] * 1LL * z % MOD));
    int res = 0, result = 0;
    for(int i=(1<<15);i>=1; i/=2) if((res+i)*2 <= n) {
        bool ok = false;
        for(int j=0;j+2*(res+i)<=n;++j)
            if(calc(j,j+2*(res+i)-1) == calc(2*n-j-2*(res+i),2*n-j-1)) {
                ok = true;
                break;
            }
        if(ok) res += i;
    }
    result >?= res * 2;
    res = 0;
    for(int i=(1<<15);i>=1; i/=2) if((res+i)*2-1 <= n) {
        bool ok = false;
        for(int j=0;j+2*(res+i)-1<=n;++j)
            if(calc(j,j+2*(res+i)-1-1) == calc(2*n-j-2*(res+i)+1,2*n-j-1)) {
                ok = true;
                break;
            }
        if(ok) res += i;
    }
    result >?= res * 2 - 1;
    cout << result << endl;
    // system("pause");
    return 0;
}