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<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 1e5;
const long long MOD = 1e9 + 7707;
char s[2*N+1], t[N+1];
int n, next[N], f[2*N], g[2*N];

void enter() {
    scanf("%s%s", s, t);
}

void kmp(const char * s, const char * t, int * l) {
    int m = strlen(s), n = strlen(t);
    fill(next, next+n, -1);
    for(int i = 1; i < n; ++i) {
        int j = next[i-1];
        while(j >= 0 && t[i] != t[j+1]) j = next[j];
        if(t[i] == t[j+1]) ++j;
        next[i] = j;
    }
    fill(l, l+m, 0);
    for(int i = 0, j = -1; i <= m; ++i) {
        while(j >= 0 && s[i] != t[j+1]) {
            if(j >= 0) l[i-1-j] = max(l[i-1-j], j+1);
            j = next[j];
        }
        if(s[i] == t[j+1]) ++j;
        l[i-j] = max(l[i-j], j+1);
        if(j == n-1) j = next[j];
    }
}

void solve() {
    n = strlen(s);
    strncpy(s+n, s, n);
    kmp(s, t, f);
    reverse(s, s+2*n); reverse(t, t+n);
    kmp(s, t, g);
    long long res = 0;
    for(int i = 0; i < n; ++i)
        if(f[i] == n) res += n;
        else if(g[n-i] >= n - f[i] - 1) ++res;
    printf("%lld\n", res);
}

int main() {
    enter();
    solve();
    return 0;
}

Code mẫu của ladpro98

{$MODE OBJFPC}
program TWOOPERS;
uses math;
const
  MAXN = 300005;
  MODULO = 1000000007;

var
  n: longint; cut: longint;
  s: ansistring;
  a: array[0..MAXN] of char;
  Z: array[0..MAXN] of longint;
  hash, power26: array[0..MAXN] of int64;

procedure initialize;
var i: longint;
begin
  read(s);
  n := length(s);
  //* transform to Zero-based
  for i := 1 to n do
  if (s[i] = ' ') then begin
    a[i - 1] := '$';
    cut := i;
  end else begin
    a[i - 1] := s[i];
  end;
  n := length(s);
  for i := cut to n - 1 do begin
    a[n] := a[i];
    inc(n);
  end;
end;

procedure buildZ;
var l, r, i: longint;
begin
  //* build Z function on a
  Z[0] := 0; l := 0; r := 0;
  for i := 1 to n - 1 do begin
    Z[i] := min(Z[i - l], max(0, r - i + 1));
    while (a[i + Z[i]] = a[Z[i]]) do begin
      l := i; r := i + Z[i];
      inc(Z[i]);
    end;
  end;
end;

procedure buildHash;
var i: longint;
begin
  power26[0] := 1;
  for i := 1 to n do
    power26[i] := power26[i - 1] * 26 mod MODULO;
  for i := 1 to n do begin
    hash[i] := hash[i - 1] * 26 + ord(a[i - 1]) - ord('A');
    hash[i] := hash[i] mod MODULO;
  end;
end;

function getHash(l, r: longint): int64;
begin
  result := hash[r + 1] - hash[l] * power26[r - l + 1] + MODULO * MODULO;
  result := result mod MODULO;
end;

procedure solve;
var
  answer: int64;
  m, i, j: longint;
begin
  answer := 0;
  m := cut - 1;
  for i := m + 1 to m + m do begin
    if (Z[i] = m) then begin
      inc(answer, m);
    end else begin
      j := i + Z[i] + 1;
      if (getHash(j, i + m - 1) = getHash(Z[i] + 1, m - 1)) then
        inc(answer);
    end;
  end;
  writeln(answer);
end;

begin
  initialize;
  buildZ;
  buildHash;
  solve;
end.

Code mẫu của RR

//Written by Nguyen Thanh Trung
//Algorithm by Pham Quang Vu
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100111;
var
  f1,f2:text;
  n:longint;
  a,b:array[1..MAXN*2] of char;
  next,xuoi,nguoc:array[1..MAXN*2] 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
  s:ansistring;
  space,i:longint;
begin
  readln(f1,s);
  space:=pos(' ',s);
  n:=space-1;
  for i:=1 to n do
    a[i]:=s[i];
  for i:=n+1 to n+n do
    a[i]:=a[i-n];
  for i:=1 to n do
    b[i]:=s[i+n+1];
end;
procedure solve;
var
  i,j,k:longint;
begin
  //KMP xuoi
  next[1]:=0; j:=0;
  for i:=2 to n do
    begin
      while (j>0) and (b[i]<>b[j+1]) do j:=next[j];
      if b[i]=b[j+1] then j+=1;
      next[i]:=j;
    end;
  j:=0;
  for i:=1 to n<<1 do
    begin
      while (j>0) and (a[i]<>b[j+1]) do j:=next[j];
      if a[i]=b[j+1] then j+=1;
      xuoi[i-j+1]:=max(xuoi[i-j+1],j);
      k:=next[j];
      while k>0 do
        begin
          if (i<n<<1) and (a[i+1]=b[k+1]) then break;
          xuoi[i-k+1]:=max(xuoi[i-k+1],k);
          k:=next[k];
        end;
      if j=n then j:=next[j];
    end;
  //KMP nguoc
  next[n]:=n+1; j:=n+1;
  for i:=n-1 downto 1 do
    begin
      while (j<=n) and (b[i]<>b[j-1]) do j:=next[j];
      if b[i]=b[j-1] then j-=1;
      next[i]:=j;
    end;
  j:=n+1; next[j]:=n+1;
  for i:=n<<1 downto 1 do
    begin
      while (j<=n) and (a[i]<>b[j-1]) do j:=next[j];
      if a[i]=b[j-1] then j-=1;
      nguoc[i+n-j]:=max(nguoc[i+n-j],n+1-j);
      k:=next[j];
      while (k<=n) do
        begin
          if (i>1) and (a[i-1]=b[k-1]) then break;
          nguoc[i+n-k]:=max(nguoc[i+n-k],n+1-k);
          k:=next[k];
        end;
      if j=1 then j:=next[j];
    end;
end;
procedure ans;
var
  i:longint;
  sum:int64;
begin
  sum:=0;
  for i:=1 to n do
    if (xuoi[i]>=n) and (nguoc[i+n-1]>=n) then sum+=n
    else if (xuoi[i]+nguoc[i+n-1]=n-1) then sum+=1;
  writeln(f2,sum);
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define fi first
#define se second
#define PB push_back
#define MP make_pair
#define ep 0.00001
#define oo 111111111
#define base 100000000
#define mod 15111992
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define rep(i, n) for(int i = 0; i < n; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;
typedef long long int64;

void OPEN(){
    freopen("A.in","r",stdin);
    freopen("A.out","w",stdout);
}

#define maxn 100005

int n, f[maxn * 3], g[maxn * 3];
string s1, s2, t1, t2;

void z_Function(string x, int z[]){
    z[0] = 0;
    int l = 0, r = -1, k;
    for(int i = 1; i < 3 * n; i++){
        k = (i > r ? 0 : min(z[i - l], r - i + 1)) + 1;
        while(i + k - 1 < 3 * n && x[k - 1] == x[i + k - 1]) k++; z[i] = --k;
        if(i + z[i] - 1 > r) l = i, r = i + z[i] - 1;
    }
}

string reverse(string x){
    string res;
    for(int i = x.length() - 1; i >= 0; i--)
        res.PB(x[i]);
    return res;
}

int main(){
    //OPEN();
    cin >> s1 >> s2;
    n = s1.length();
    t1 = reverse(s1); t2 = reverse(s2);
    s1 = s1 + s1.substr(0, n - 1);
    t1 = t1.substr(1, n - 1) + t1;
    z_Function(s2 + char(0) + s1, f);
    z_Function(t2 + char(0) + t1, g);
    int res = 0;
    bool flag = false;
    for(int i = n + 1; i <= n + n; i ++){
        if(f[i] >= n){
            res++;
            flag = true;
        }
        if(f[i] + g[3 * n + 1 - i] == n - 1) res++;
    } 
    if(!flag)
        printf("%d", res);
    else printf("%lld\n",res * 1ll * n);
}

Code mẫu của ll931110

program TWOOPERS;
const
  input  = '';
  output = '';
  maxn = 200000;
  base = 632243281;
var
  hs,ht,ls,lt: array[0..maxn] of int64;
  a,s,t: ansistring;
  n: longint;
  res: int64;

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

  readln(f, a);
  n := (length(a) - 1) div 2;

  s := copy(a,1,n);
  s := s + s;

  t := copy(a,n + 2,n);
  t := t + t;

  close(f);
end;

function calc(x,p: longint): int64;
var
  q: int64;
begin
  if p = 0 then exit(1);
  q := calc(x,p div 2);
  q := (q * q) mod base;
  if odd(p) then q := (q * x) mod base;
  calc := q;
end;

procedure hash;
var
  i: longint;
  tmp,pow: int64;
begin
  pow := calc(26,n - 1);

  hs[0] := 0;
  hs[1] := ord(s[1]) - ord('A');
  for i := 2 to 2 * n - 1 do
    hs[i] := (hs[i - 1] * 26 + ord(s[i]) - ord('A')) mod base;

  for i := 1 to n do
    begin
      tmp := (hs[i - 1] * pow) mod base;
      ls[i] := hs[i + n - 2] - tmp;
      if ls[i] < 0 then ls[i] := ls[i] + base;
    end;

  ht[0] := 0;
  ht[1] := ord(t[1]) - ord('A');
  for i := 2 to 2 * n - 1 do
    ht[i] := (ht[i - 1] * 26 + ord(t[i]) - ord('A')) mod base;

  for i := 1 to n do
    begin
      tmp := (ht[i - 1] * pow) mod base;
      lt[i] := ht[i + n - 2] - tmp;
      if lt[i] < 0 then lt[i] := lt[i] + base;
    end;
end;

procedure swap(var x,y: int64);
var
  z: int64;
begin
  z := x;  x := y;  y := z;
end;

procedure sort(l,h: longint);
var
  i,j: longint;
  p: int64;
begin
  if l >= h then exit;
  i := l;  j := h;  p := lt[random(h - l + 1) + l];

  repeat
    while lt[i] < p do inc(i);
    while lt[j] > p do dec(j);
    if i <= j then
      begin
        if i < j then swap(lt[i],lt[j]);
        inc(i);
        dec(j);
      end;
  until i > j;

  sort(l,j);  sort(i,h);
end;

procedure solve;
var
  i: longint;
  inf,sup,med,t1,t2: longint;
begin
  res := 0;
  for i := 1 to n do
    begin
      t1 := 0;
      inf := 1;
      sup := n;

      repeat
        med := (inf + sup) div 2;
        if lt[med] = ls[i] then t1 := med;
        if lt[med] >= ls[i] then sup := med - 1 else inf := med + 1;
      until inf > sup;

      t2 := 0;
      inf := 1;
      sup := n;

      repeat
        med := (inf + sup) div 2;
        if lt[med] = ls[i] then t2 := med;
        if lt[med] <= ls[i] then inf := med + 1 else sup := med - 1;
      until inf > sup;

      if t1 <> 0 then res := res + t2 - t1 + 1;
    end;
end;

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

begin
  init;
  hash;
  sort(1,n);
  solve;
  printresult;
end.

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#define BASE   29
#define NMOD   1
#define MAX   100100
typedef long long ll;
const ll mod[]={1e9+7,1e9+21,1e9+97,1e9+9,1e9+33};
char a[2*MAX];
char b[2*MAX];
ll pw[5][2*MAX];
ll sa[5][2*MAX];
ll sb[5][2*MAX];
int n;
void init(void) {
    scanf("%s",a);
    scanf("%s",b);
    n=strlen(a);
    int i,j;
    for (i=0;i<n;i=i+1) {
        a[i+n]=a[i];
        b[i+n]=b[i];
    }
    a[2*n]=0;
    b[2*n]=0;
    n=2*n;
    for (i=0;i<NMOD;i=i+1) {
        pw[i][0]=1;
        sa[i][0]=0;
        sb[i][0]=0;
        for (j=1;j<=n;j=j+1) {
            pw[i][j]=(pw[i][j-1]*BASE);
            sa[i][j]=(sa[i][j-1]+(a[j-1]-'A')*pw[i][j-1]);
            sb[i][j]=(sb[i][j-1]+(b[j-1]-'A')*pw[i][j-1]);
        }
    }
}
bool same(const int &fa,const int &fb,const int &m) {
    if (m==0) return (true);
    ll x,y;
    int i;
    for (i=0;i<NMOD;i=i+1) {
        x=(sa[i][fa+m-1]-sa[i][fa-1]);
        y=(sb[i][fb+m-1]-sb[i][fb-1]);
        if (fa<fb) x=(x*pw[i][fb-fa]);
        if (fb<fa) y=(y*pw[i][fa-fb]);
        if ((x-y)!=0) return (false);
    }
    return (true);
}
void process(void) {
    ll res=0;
    int i,l,m,r;
    for (i=1;i<=n/2;i=i+1) {
        l=0;
        r=n/2;
        while (true) {
            if (r==l) {
                m=r;
                break;
            }
            if (r-l==1) {
                if (same(i,1,r)) m=r;
                else m=l;
                break;
            }
            m=(l+r)/2;
            if (same(i,1,m)) l=m;
            else r=m-1;
        }
        if (m==n/2) res=res+n/2;
        else res=res+same(i+m+1,m+2,n/2-m-1);
    }
    printf("%lld\n",res);
}
int main(void) {
    init();
    process();
    return 0;
}