Hướng dẫn giải của Palindrome dài nhất


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

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;
}

Bình luận

Hãy đọc nội quy trước khi bình luận.



  • 0
    Phanvanthinh  đã bình luận lúc 28, Tháng 1, 2024, 2:25

    include <iostream>

    include <bits/stdc++.h>

    using namespace std; string x; int F[1000][1000];

    bool DX(string G){ string H = G; int n = G.size(); for(int i = 0; i < (n/2); i++) swap(G[i], G[n-i-1]); return H == G; }

    int Xl1(string G){ string Tam = ""; int Max = 0; for(int i = 0; i < G.size(); i++){ for(int j = G.size(); j >= 0; j--){ Tam = G.substr(i, j-i); if (DX(Tam)) Max = max(j-i, Max); } } return Max; }

    int Xl2(string a){ string b = ""; for(int i = 0; i < a.size(); i++) b = a[i] + b; for(int i = 0; i < a.size(); i++) for(int j = 0; j < b.size(); j++) if (a[i] == b[j]) F[i+1][j+1] = F[i][j] + 1; else F[i+1][j+1] = max(F[i+1][j], F[i][j+1]); return F[a.size()][b.size()]; }

    int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); //freopen("SUBSTR.inp", "r", stdin); //freopen("SUBSTR.out", "w", stdout); getline(cin, x); cout<<Xl1(x)<<'\n'; //cout<<Xl2(x); return 0; }