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

const fi='';
      z=1337377;
type pointer=^node;
     node=record
            cnt:longint;
            next:array['a'..'z'] of pointer;
          end;
var n,i,j:longint;
    a,s:ansistring;
    top:pointer;
    f:array[0..300030] of longint;

function create:pointer;
var c:char; p:pointer;
begin
     new(p); p^.cnt:=0;
     for c:='a' to 'z' do p^.next[c]:=nil;
     exit(p);
end;

procedure put(p:pointer;pos:longint;s:ansistring);
var t:pointer;
begin
     if p^.next[s[pos]]=nil then p^.next[s[pos]]:=create;
     t:=p^.next[s[pos]];
     if pos<length(s) then put(t,pos+1,s)
     else inc(t^.cnt);
end;

procedure check(p:pointer;pos,x:longint);
var t:pointer;
begin
     if p^.next[a[pos+x]]=nil then exit;
     t:=p^.next[a[pos+x]];
     if t^.cnt>0 then
     begin
          f[pos+x]:=f[pos+x]+f[x];
          if f[pos+x]>=z then f[pos+x]:=f[pos+x]-z;
     end;
     if (pos<100) and (pos+x<n) then check(t,pos+1,x);
end;

begin
     assign(input,fi); reset(input);
     readln(a);
     readln(n);
     top:=create;
     for i:=1 to n do
     begin
          readln(s);
          put(top,1,s);
     end;
     n:=length(a);
     f[0]:=1;
     for i:=0 to n-1 do check(top,1,i);
     writeln(f[n]);
     close(input);
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>

const int N = 4000 + 2, L = 300000 + 2, WL = 100 + 2, MOD = 1337377;
struct TrieNode {
    int next[26], nfinish;
} trie[N * WL];
int nnode = 1, n, f[L];
char tmp[WL], s[L];

void insert(const char * s) {
    int u = 0;
    for(int i = strlen(s) - 1; i >= 0; --i) {
        int t = s[i] - 0x61;
        if(trie[u].next[t] == 0) trie[u].next[t] = nnode++;
        u = trie[u].next[t];
    }
    trie[u].nfinish = 1;
}

void enter() {
    scanf("%s%d", s+1, &n);
    for(int i = 0; i < n; ++i) {
        scanf("%s", tmp);
        insert(tmp);
    }
}

void solve() {
    f[0] = 1; int l = strlen(s + 1);
    for(int i = 1; i <= l; ++i) {
        int u = 0;
        for(int j = i; j && trie[u].next[s[j] - 0x61]; --j)
            if(trie[u = trie[u].next[s[j] - 0x61]].nfinish)
                f[i] = (f[j-1] + f[i]) % MOD;
    }
    printf("%d\n", f[l]);
}

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

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 300005;
const int MOD = 1337377;
using namespace std;
char s[N], aa[111];
int f[N];
int n;

struct node {
    int a[26]; int e;
    int& operator[] (int i) {return a[i];}
    node() {for(int i=0; i<26; i++) a[i] = 0; e = 0;}
};

vector<node> a;

void Add(char *s) {
    int pos = 0, i, c;
    for(i=0; c = s[i]; i++) {
        if (a[pos][c - 'a'] == 0) {
            a.push_back(node());
            a[pos][c - 'a'] = a.size() - 1;
        }
        pos = a[pos][c - 'a'];
    }
    a[pos].e = 1;
}

int main()
{
    gets(s); scanf("%d\n", &n);
    int i, j, pos, c;
    a.push_back(node());
    for(i=1;i<=n; i++) {
        gets(aa); Add(aa);
    }
    f[0] = 1;
    for(i=0; s[i]; i++) {
        pos = 0;
        for(j=i; c = s[j]; j++) {
            if (a[pos][c - 'a'] == 0) break;
            pos = a[pos][c - 'a'];
            if (a[pos].e == 1) f[j+1] = (f[j+1] + f[i]) % MOD;
        }
    }
    printf("%d\n", f[strlen(s)]);
    return 0;
}

Code mẫu của RR

//Wishing myself a happy lunar new year with a lot of accept solutions
//Written by Nguyen Thanh Trung
{$R-,Q-}
const
  FINP='';
  FOUT='';
  MAXN=300111;
  oo=1337377;
type
  trie=^node;
  node=record
         c:integer;
         d:array['a'..'z'] of trie;
       end;
var
  s:ansistring;
  n:longint;
  root:trie;
  d:array[0..MAXN] of longint;
procedure add(var t:trie);
var
  ch:char;
begin
  new(t); t^.c:=0;
  for ch:='a' to 'z' do t^.d[ch]:=nil;
end;
procedure inp;
var
  a:string;
  i,j,m,l:longint;
  x:trie;
begin
  assign(input,FINP); reset(input);
  readln(s); n:=length(s);
  readln(m);
  add(root);
  for i:=1 to m do
    begin
      readln(a); l:=length(a);
      x:=root;
      for j:=l downto 1 do
        begin
          if x^.d[a[j]]=nil then add(x^.d[a[j]]);
          x:=x^.d[a[j]];
        end;
      inc(x^.c);
    end;
  close(input);
end;
procedure solve;
var
  i,j:longint;
  x:trie;
begin
  d[0]:=1;
  for i:=1 to n do
    begin
      x:=root; j:=i;
      while (j>0) and (x^.d[s[j]]<>nil) do
        begin
          x:=x^.d[s[j]];
          dec(j);
          if x^.c=1 then inc(d[i],d[j]);
        end;
      d[i]:=d[i] mod oo;
    end;
  writeln(d[n]);
end;
begin
  inp;
  solve;
end.

Code mẫu của ll931110

#include <cmath>
#include <cstring>
#include <iostream>
#define MOD 1337377
using namespace std;

struct trie
{
    int val;
    int d[26];
} tx[400110];

int n,k,cnt = -1;
char S[300010];
char a[105];
int F[300010];

int create()
{
    cnt++;  tx[cnt].val = 0;
    memset(tx[cnt].d,-1,sizeof(tx[cnt].d));
    return cnt;
}

int main()
{
//  freopen("strings.inp","r",stdin);
//  freopen("strings.out","w",stdout);
    scanf("%s", &S);  n = strlen(S);
    int tmp = create();

    scanf("%d", &k);
    for (int i = 0; i < k; i++)
    {
        scanf("%s", &a);
        int s = 0;
        for (int j = 0; j < strlen(a); j++)
        {
            int next = tx[s].d[a[j] - 'a'];
            if (next < 0) 
            {               
                next = create();
                tx[s].d[a[j] - 'a'] = next;
            }
            s = next;
        }
        tx[s].val++;        
    }

    memset(F,0,sizeof(F));
    F[n] = 1;
    for (int i = n - 1; i >= 0; i--)    
    {       
        int s = 0,j = i;
        while (j < n)
        {
            s = tx[s].d[S[j] - 'a'];
            if (s < 0) break;
            j++;
            F[i] = (F[i] + tx[s].val * F[j]) % MOD;
        }
    }
    printf("%d\n", F[0]);
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>

using namespace std;

struct Trie {
    bool last;
    Trie * n[26];
};

Trie container[800000];
int ncon;

int n, N;
char a[300030], tmp[444];
Trie root;
int f[300030];
const int mod = 1337377;

void add( char * a) {
    Trie * p = &root;
    for(int i=0;a[i]!=0;++i) {
        int t = a[i] - 'a';
        if(p->n[t]!=NULL) p = p->n[t];
        else {
            p->n[t] = container + ++ncon;
            p = p->n[t];
        }
    }
    p->last = true;
}

int main() {
    gets(a);
    n = strlen(a);
    scanf("%d", &N);
    gets(tmp);
    for(int i=0;i<N;++i) {
        gets(tmp);
        add( tmp);
    }
    f[n] = 1;
    for(int i=n-1;i>=0;--i) {
        Trie * p = &root;
        for(int j=i;j<n;++j) {
            int t = a[j] - 'a';
            if(p->n[t]==NULL) break;
            p = p->n[t];
            if(p->last) f[i] += f[j+1];
        }
        f[i] %= mod;
    }
    cout << f[0] << endl;
    //system("pause");
    return 0;
}