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 happyboy99x

#include <algorithm>
#include <cstring>
#include <cassert>
#include <vector>
#include <cstdio>
#include <queue>
using namespace std;

const int L = (int) 1e6 + 5;
char a[2 * L];
char s[L];
int p[2 * L];
int ptr;

void manacher(char s[], int n) {
    ptr = 0;
    for (int i = 0; i < n; ++i) {
        if (i > 0) a[ptr++] = '$';
        a[ptr++] = s[i];
    }
    for (int i = 0, j = 0, mx = 0; i < ptr; ++i) {
        p[i] = i < mx ? min(mx - i, p[2 * j - i]) : 1;
        while (i >= p[i] && i + p[i] < ptr && a[i - p[i]] == a[i + p[i]]) {
            ++p[i];
        }
        if (i + p[i] > mx) {
            mx = i + p[i];
            j = i;
        }
    }
}

bool isPalindrome(int l, int r) {
    return r - l + 1 <= p[l + r];
}

struct Trie {
    int next[L][26];
    int numEnd[L];
    int numPalinSuffix[L];
    int numNodes;

    Trie() {
        numNodes = 1;
    }

    void add(char s[], int n) {
        int u = 0;
        for (int i = 0; i < n; ++i) {
            int c = s[i] - 'a';
            if (next[u][c] == 0) {
                next[u][c] = numNodes++;
            }
            u = next[u][c];
            if (i + 1 < n && isPalindrome(i + 1, n - 1)) {
                ++numPalinSuffix[u];
            }
        }
        ++numEnd[u];
    }
} trie1, trie2;

int main() {
    #ifdef __DNK__
    assert(freopen("palinx.in", "r", stdin));
    #endif // __DNK__
    int n;
    assert(scanf("%d", &n) == 1);
    for (int i = 0; i < n; ++i) {
        int len;
        assert(scanf("%d %s", &len, s) == 2);
        manacher(s, len);
        trie1.add(s, len);
        reverse(s, s + len);
        reverse(p, p + ptr);
        trie2.add(s, len);
    }
    long long answer = 0;
    queue<pair<int, int> > q;
    q.push(make_pair(0, 0));
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        answer += 1LL * trie1.numEnd[x] * trie2.numEnd[y];
        answer += 1LL * trie1.numEnd[x] * trie2.numPalinSuffix[y];
        answer += 1LL * trie1.numPalinSuffix[x] * trie2.numEnd[y];
        for (int i = 0; i < 26; ++i) {
            if (trie1.next[x][i] != 0 && trie2.next[y][i] != 0) {
                q.push(make_pair(trie1.next[x][i], trie2.next[y][i]));
            }
        }
    }
    printf("%lld\n", answer);
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define long long long
#define SetLength(a, n, t) free(a), a=(t*) calloc(n, sizeof(t))

const int MOD = 1000000003;
const long MM = (long)MOD * (long)MOD;
const int N = 1000006;
using namespace std;
long* H[N]; long *R[N]; //forward and reverse Hash
int n, max_len, len[N];
long POW[N];
char* s[N];

void Build_Hash() {
    POW[0] = 1;
    int i, j;
    for(i = 1; i <= max_len; i++) POW[i] = (26 * POW[i - 1]) % MOD;
    for(i = 1; i <= n; i++) {
        //H[i].resize(len[i] + 2);
        SetLength(H[i], len[i] + 2, long);
        for(j = 1; j <= len[i]; j++)
            H[i][j] = (26 * H[i][j - 1] + s[i][j] - 'a') % MOD;
        //R[i].resize(len[i] + 2);
        SetLength(R[i], len[i] + 2, long);
        for(j = len[i]; j; j--)
            R[i][j] = (26 * R[i][j + 1] + s[i][j] - 'a') % MOD;
    }
}

bool isPalin(int pos, int i, int j) {
    int h = (H[pos][j] - POW[j - i + 1] * H[pos][i - 1] + MM) % MOD;
    int r = (R[pos][i] - POW[j - i + 1] * R[pos][j + 1] + MM) % MOD;
    return h == r;
}

class Trie {
public:
    struct node {
        int a[26]; int cnt, e;
        int& operator [] (int i) {return a[i];}
        node() {for(int i = 0; i < 26; i++) a[i] = 0; cnt = e = 0;}
    };

    vector<node> a;
    void Add(int st) {
        int pos = 0, i, c;
        for(i = 1; i <= len[st]; i++) {
            c = s[st][i] - 'a';
            if (a[pos][c] == 0) {
                a.push_back(node());
                a[pos][c] = a.size() - 1;
            }
            pos = a[pos][c];
            if (i < len[st] && isPalin(st, i + 1, len[st])) a[pos].cnt++;
        }
        a[pos].e++;
    }

    int DFS(int st, int i, int pos, int es) {
        //printf("%d %d %d %d\n", st, i, pos, es);
        if (i == 1)
            return a[pos].cnt + a[pos].e + es;
        if (a[pos][s[st][i - 1] - 'a'] != 0)
        return DFS(st, i - 1, a[pos][s[st][i - 1] - 'a'],
                   es + (isPalin(st, 1, i - 1) ? a[pos].e : 0));
        else
            return (isPalin(st, 1, i - 1) ? a[pos].e : 0) + es;
    }

    void clear() {a.clear(); a.push_back(node());}
    Trie() {clear();}
};

Trie T;

int main()
{
    scanf("%d\n", &n);
    int i; char c;
    for(i = 1; i <= n; i++) {
        scanf("%d", &len[i]);
        s[i] = new char[len[i] + 1];scanf("%c", &c);
        gets(s[i] + 1);
        max_len = max(max_len, len[i]);
    }
    Build_Hash();
    for(i = 1; i <= n; i++) T.Add(i);
    //for(i = 1; i <= n; i++) cout << T.a[i].e << " " << T.a[i].cnt << endl;
    long res = 0;
    for(i = 1; i <= n; i++)
    if (T.a[0][s[i][len[i]] - 'a'] != 0)
        res += T.DFS(i, len[i], T.a[0][s[i][len[i]] - 'a'], 0);
    printf("%lld" ,res);
    return 0;
}

Code mẫu của RR

//Written by RR
{$R-,Q-}
{$Mode objfpc}
{$inline on}

uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       2000111;

type
  trie          =       ^node;
  node          =       record
        u       :       longint;
        c       :       array['a'..'z'] of trie;
  end;

procedure add(var u:trie); inline;
    var
      c:char;
    begin
      new(u);
      u^.u:=0;
      for c:='a' to 'z' do
        u^.c[c]:=nil;
    end;
procedure del(var u:trie); inline;
    var
      c:char;
    begin
      if u=nil then exit;
      for c:='a' to 'z' do
        del(u^.c[c]);
      dispose(u);
    end;

var
  f1,f2         :       text;
  n             :       longint;
  a             :       array[1..MAXN] of char;
  start         :       array[1..MAXN,0..1] of longint;
  next          :       array[1..MAXN] of longint;
  isPalin       :       array[1..MAXN] of longint;
  root          :       trie;
  res           :       int64;
  save          :       longint;
  saveT         :       trie;

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
      now,i,l:longint;
      c:char;
    begin
      readln(f1,n);
      now:=1;
      for i:=1 to n do
        begin
          start[i,0]:=now;
          read(f1,l,c);
          start[i,1]:=now+l-1; now:=start[i,1]+1;
          for l:=start[i,0] to start[i,1] do
            read(f1,a[l]);
        end;
    end;

procedure insert(l,r,k:longint); inline;
    var
      p:trie;
      i:longint;
    begin
      p:=root;
      i:=l-k;
      repeat
        i:=i+k;
        if p^.c[a[i]]=nil then add(p^.c[a[i]]);
        p:=p^.c[a[i]];
      until i=r;
      inc(p^.u);
    end;

function count(l,r,k:longint):longint; inline;
    var
      i:longint;
      p:trie;
    begin
      if (l*k>r*k) then exit(0);
      p:=saveT;
      i:=save-k;
      repeat
        i:=i+k;
        if p^.c[a[i]]=nil then exit(-1);
        saveT:=p;
        p:=p^.c[a[i]];
      until i=r;
      save:=r;
      exit(p^.u);
    end;

procedure khop(dau,cuoi,k:longint);
    var
      x,i,j,moc:longint;
    begin
      //preKMP
      for x:=1 to n do
        begin
          moc:=start[x,cuoi]+k;
          i:=moc; j:=i;
          next[i-k]:=j;
          i:=i-k;
          if i<>start[x,dau] then
          repeat
            i:=i-k;
            while (j<>moc) and (a[i]<>a[j-k]) do j:=next[j];
            if (a[i]=a[j-k]) then j:=j-k;
            next[i]:=j;
          until i=start[x,dau];
        end;

      //writeln(stderr,'Done preKMP ',k);

      //KMP
      fillchar(isPalin,sizeof(isPalin),0);
      for x:=1 to n do
        begin
          moc:=start[x,cuoi]+k;
          i:=start[x,dau]-k; j:=moc;
          if i<>start[x,cuoi] then
          repeat
            i:=i+k;
            while (j<>moc) and (a[i]<>a[j-k]) do j:=next[j];
            if (a[i]=a[j-k]) then j:=j-k;
            while (j<>moc) and (i*k>=j*k) do
              begin
                isPalin[i+(j-moc)+k]:=1;
                j:=next[j];
              end;
          until i=start[x,cuoi];
        end;
      //writeln(stderr,'Done KMP ',k);

      //Make trie
      del(root);
      //writeln(stderr,'Done delete trie ',k);
      add(root);
      for x:=1 to n do
        insert(start[x,cuoi],start[x,dau],-k);

      //writeln(stderr,'Done make trie ',k);

      //Count
      for x:=1 to n do
        begin
          i:=start[x,dau]-k;
          save:=start[x,dau];
          saveT:=root;
          repeat
            i:=i+k;
            if isPalin[i]=1 then
              begin
                j:=count(save,i-k,k);
                if j=-1 then break;
                res:=res+j;
                if j>0 then
                  write;
              end;
          until i=start[x,cuoi];
        end;
      //writeln(stderr,'Done counting ',k);
    end;

procedure solve;
    var
      x,j:longint;
    begin
      for x:=1 to n do
        begin
          saveT:=root; save:=start[x,1];
          j:=count(start[x,1],start[x,0],-1);
          if j>0 then res:=res+j;
        end;

      writeln(f2,res);
    end;

begin
  openF;
  inp;
  khop(0,1,1);
  khop(1,0,-1);
  solve;
  closeF;
end.

Code mẫu của skyvn97

{$R-}
{$Q-}
{$M 100000,1000000}
program palinx_voj;
const
      maxl=1000100;
      base=37;
      mdul=1000000007;
type
      nod=record
            pa,nb,nf:longint;
            ch:array [ord('a')-3..ord('z')+3] of longint;
      end;
var
      n,nnod:longint;
      trie:array [0..2*maxl] of nod;
      head:array [0..maxl] of longint;
      fid,bid:array [0..maxl] of longint;
      pw:array [0..maxl] of int64;
      fhash,bhash:array [0..2*maxl] of int64;
      s:ansistring;
function nod_init(p:longint):nod;
      var
            ret:nod;
            i:longint;
      begin
            ret.pa:=p;
            ret.nb:=0;
            ret.nf:=0;
            for i:=ord('a') to ord('z') do ret.ch[i]:=-1;
            exit(ret);
      end;
procedure insert(i:longint;c:char);
      begin
            inc(nnod);
//            if (nnod mod 50000) =0 then writeln('tree has ',nnod);
            trie[nnod-1]:=nod_init(i);
            trie[i].ch[ord(c)]:=nnod-1;
//            writeln('Inserted child ',c,' of ',i,' at location ',nnod-1);
      end;
procedure init;
      var
            i,j,u,l:longint;
      begin
            read(n);
//            writeln(n);
            nnod:=1;
            trie[0]:=nod_init(-1);
            head[0]:=0;
            pw[0]:=1;
            for i:=1 to maxl do pw[i]:=(pw[i-1]*base) mod mdul;
            for i:=1 to n do
                  begin
                        read(l);
                        read(s);
//                        writeln('srting read ',length(s));
                        head[i]:=head[i-1]+l+1;
                        fhash[head[i-1]+1]:=0;
                        u:=0;
                        for j:=1to l do
                              begin
//                                    writeln('s (',j,')= ',s[j]);
                                    if trie[u].ch[ord(s[j+1])]<0 then insert(u,s[j+1]);
                                    u:=trie[u].ch[ord(s[j+1])];
                                    fhash[head[i-1]+j+1]:=(fhash[head[i-1]+j]+pw[j-1]*(ord(s[j+1])-ord('a'))) mod mdul;
                              end;
                        inc(trie[u].nf);
                        fid[i]:=u;
                        bhash[head[i]]:=0;
                        u:=0;
                        for j:=l downto 1 do
                              begin
                                    if trie[u].ch[ord(s[j+1])]<0 then insert(u,s[j+1]);
                                    u:=trie[u].ch[ord(s[j+1])];
                                    bhash[head[i-1]+j]:=(bhash[head[i-1]+j+1]+pw[l-j]*(ord(s[j+1])-ord('a'))) mod mdul;
                              end;
                        inc(trie[u].nb);
                        bid[i]:=u;
//                        writeln('String ',i,' is at ',fid[i],' and ',bid[i]);
                  end;
//            writeln('Input read');
      end;
function samestr(i,a,b:longint):boolean;
      var
            x,y:int64;
      begin
//            writeln('checking str ',i,' from ',a,' to ',b);
            if a>b then exit(true);
            x:=(fhash[head[i-1]+b+1]-fhash[head[i-1]+a]+mdul) mod mdul;
            y:=(bhash[head[i-1]+a]-bhash[head[i-1]+b+1]+mdul) mod mdul;
            if a-1>head[i]-head[i-1]-1-b then y:=(y*pw[(a-1)-(head[i]-head[i-1]-1-b)]) mod mdul;
            if a-1<head[i]-head[i-1]-1-b then x:=(x*pw[(head[i]-head[i-1]-1-b)-(a-1)]) mod mdul;
//            if (x-y) mod mdul=0 then writeln('true') else writeln('false');
            exit((x-y) mod mdul=0);
      end;
procedure process;
      var
            res:int64;
            i,j,u,l:longint;
      begin
            res:=0;
            for i:=1 to n do
                  begin
                        l:=head[i]-head[i-1]-1;
                        u:=fid[i];
                        while u>0 do
                              begin
                                    if trie[u].nb>0 then
                                          if samestr(i,l+1,head[i]-head[i-1]-1) then
                                                begin
                                                      res:=res+trie[u].nb;
//                                                      writeln('added ',trie[u].nb);
                                                end;
                                    u:=trie[u].pa;
                                    dec(l);
                              end;
                        l:=head[i]-head[i-1]-1;
                        u:=bid[i];
                        u:=trie[u].pa;
//                        writeln('backward');
                        dec(l);
                        while u>0 do
                              begin
                                    if trie[u].nf>0 then
                                          if samestr(i,1,head[i]-head[i-1]-1-l) then
                                                begin
                                                      res:=res+trie[u].nf;
//                                                      writeln('added ',trie[u].nf);
                                                end;
                                    u:=trie[u].pa;
                                    dec(l);
                              end;
//                        writeln('After ',i,': ',res);
                  end;
            write(res);
      end;
begin
//      assign(input,'tmp.txt');
//      reset(input);
      init;
      process;
      readln;
//      close(input);
end.