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 max=500050;
var m,n,i,j,x,re,num:longint;
    f:array[0..max,0..1] of longint;
    g,s:array[0..max] of longint;
    a:array[1..11111] of longint;

procedure put(nd,pos:longint);
var z,y:longint;
begin
     z:=a[pos];
     if f[nd,z]=0 then
     begin
          inc(num); f[nd,z]:=num;
     end;
     y:=f[nd,z];
     if pos=x then inc(g[y])
     else put(y,pos+1);
     s[nd]:=s[y]+g[y];
     if f[nd,1-z]>0 then inc(s[nd],s[f[nd,1-z]]+g[f[nd,1-z]]);
end;

procedure check(nd,pos:longint);
var y,z:longint;
begin
     z:=a[pos];
     if f[nd,z]=0 then exit;
     y:=f[nd,z];
     re:=re+g[y];
     if pos=x then re:=re+s[y]
     else check(y,pos+1);
end;

begin
     read(n,m);
     for i:=1 to n do
     begin
          read(x);
          for j:=1 to x do read(a[j]);
          put(0,1);
     end;
     for i:=1 to m do
     begin
          read(x);
          for j:=1 to x do read(a[j]);
          re:=0;
          check(0,1);
          writeln(re);
     end;
end.

Code mẫu của happyboy99x

#include<cstdio>

struct trieNode { int next[2], nfinish, ncross; } trie[500000+5];
int m, n, a[10000+5], nnode;

void mark(int * a, int n) {
    int u = 0; ++trie[0].ncross;
    for(int i = 0; i < n; ++i) {
        if(trie[u].next[a[i]] == 0) trie[u].next[a[i]] = ++nnode;
        u = trie[u].next[a[i]];
        ++trie[u].ncross;
    }
    ++trie[u].nfinish;
}

void query(int * a, int n) {
    int u = 0, res = 0, ok = 1;
    for(int i = 0; i < n; ++i)
        if(trie[u].next[a[i]]) {
            u = trie[u].next[a[i]];
            res += trie[u].nfinish;
        } else {
            ok = 0;
            break;
        }
    if(ok) res += trie[u].ncross - trie[u].nfinish;
    printf("%d\n", res);
}

int enter(int * a) {
    int l; scanf("%d", &l);
    for(int i = 0; i < l; ++i) scanf("%d", a+i);
    return l;
}

int main() {
    scanf("%d%d", &m, &n);
    for(int i = 0; i < m; ++i) mark(a, enter(a));
    for(int i = 0; i < n; ++i) query(a, enter(a));
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
type
  trie=^node;
  node=record
         last,g:longint;
         l,r:trie;
       end;
var
  f1,f2:text;
  m,n:longint;
  root:trie;
procedure openF;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
  close(f1); close(f2);
end;
procedure add(var a:trie);
var
  p:trie;
begin
  new(p); p^.l:=nil; p^.r:=nil;
  p^.last:=0; p^.g:=0;
  a:=p;
end;
procedure inp;
var
  i,l,j,u:longint;
  p:trie;
begin
  add(root);
  read(f1,m,n);
  for i:=1 to m do
    begin
      read(f1,l); p:=root;
      for j:=1 to l do
        begin
          read(f1,u);
          if u=0 then
            begin
              if p^.l=nil then add(p^.l);
              p:=p^.l; inc(p^.g);
            end
          else
            begin
              if p^.r=nil then add(p^.r);
              p:=p^.r; inc(p^.g);
            end;
        end;
      dec(p^.g); inc(p^.last);
    end;
end;
procedure ans;
var
  i,l,j,u,kq:longint;
  p:trie;
  ok:boolean;
begin
  for i:=1 to n do
    begin
      read(f1,l); kq:=0; p:=root;
      ok:=true;
      for j:=1 to l do
        begin
          read(f1,u);
          if not ok then continue;
          if u=0 then
            begin
              if p^.l=nil then ok:=false
              else p:=p^.l;
            end
          else
            begin
              if p^.r=nil then ok:=false
              else p:=p^.r;
            end;
          if ok then inc(kq,p^.last);
        end;
      if ok then inc(kq,p^.g);
      writeln(f2,kq);
    end;
end;
begin
  openF;
  inp;
  ans;
  closeF;
end.

Code mẫu của ll931110

{$MODE DELPHI}
program SEC;
const
  input  = '';
  output = '';
  maxn = 50000;
type
  ptree = ^ttree;
  ttree = record
    v1,v2,ve: integer;
    left,right: ptree;
  end;
var
  fi,fo: text;
  root: ptree;
  m,n: integer;

procedure openfile;
begin
  assign(fi, input);
    reset(fi);

  assign(fo, output);
    rewrite(fo);
end;

procedure Trie_construct;
var
  i,j,x,v: integer;
  p,q: ptree;
begin
  new(root);
  root^.left := nil;
  root^.right := nil;
  root^.v1 := 0;

  readln(fi, m, n);

  for i := 1 to m do
    begin
      p := root;
      read(fi, x);
      for j := 1 to x do
        begin
          read(fi, v);
          if v = 0 then q := p^.left else q := p^.right;

          if q = nil then
            begin
              new(q);
              q^.left := nil;
              q^.right := nil;
              q^.v1 := 0;
              q^.v2 := 1;
              q^.ve := 0;
              if v = 0 then p^.left := q else p^.right := q;
            end
          else inc(q^.v2);

          p := q;
        end;

      inc(p^.v1);
      inc(p^.ve);
    end;
end;

procedure Trie_calc(p: ptree);
begin
  if p^.left <> nil then
    begin
      p^.left.v1 := p^.left.v1 + p^.v1;
      Trie_calc(p^.left);
    end;

  if p^.right <> nil then
    begin
      p^.right.v1 := p^.right.v1 + p^.v1;
      Trie_calc(p^.right);
    end;
end;

procedure solve;
var
  i,j,x,v: integer;
  t1,t2,et: integer;
  p: ptree;
begin
  for i := 1 to n do
    begin
      t1 := 0;
      t2 := 0;
      et := 0;

      p := root;
      read(fi, x);

      for j := 1 to x do
        begin
          read(fi, v);
          if v = 0 then p := p^.left else p := p^.right;

          if p = nil then
            begin
              t2 := 0;
              readln(fi);
              break;
            end;

          t1 := p^.v1;
          t2 := p^.v2;
          if j = x then et := p^.ve;
        end;

      writeln(fo, t1 + t2 - et);
    end;
end;

procedure closefile;
begin
  close(fo);
  close(fi);
end;

begin
  openfile;
  Trie_construct;
  Trie_calc(root);
  solve;
  closefile;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   50005
using namespace std;
struct nod {
    int pa;
    int ch[2];
    int nc;
    int np;
    int ims;
    nod(){}
    nod(const int &_pa) {
        pa=_pa;
        ch[0]=-1;
        ch[1]=-1;
        nc=0;
        np=0;
        ims=0;
    }
};
vector<nod> trie;
int id[MAX];
int m,n;
void insert(const int &i,const int &j) {
    trie.push_back(nod(i));
    trie[i].ch[j]=trie.size()-1;
    //printf("Inserted nod %d 's child %d at location %d\n",i,j,trie.size()-1);
}
void init(void) {
    trie.clear();
    trie.push_back(nod(-1));
    int i,j,t,u,v;
    scanf("%d",&m);
    scanf("%d",&n);
    for (i=1;i<=m;i=i+1) {
        scanf("%d",&t);        
        u=0;
        for (j=1;j<=t;j=j+1) {
            scanf("%d",&v);
            if (trie[u].ch[v]<0) insert(u,v);
            u=trie[u].ch[v];
        }
        trie[u].ims++;
    }    
    for (i=1;i<=n;i=i+1) {    
        scanf("%d",&t);
        u=0;
        for (j=1;j<=t;j=j+1) {
            scanf("%d",&v);
            if (trie[u].ch[v]<0) insert(u,v);
            u=trie[u].ch[v];
        }       
        id[i]=u;
    }
}
void visit(const int &u) {
        int i,v;
        for (i=0;i<2;i=i+1) {
                v=trie[u].ch[i];
                if (v<0) continue;
                trie[v].np=trie[u].np+trie[u].ims;
                visit(v);
                trie[u].nc=trie[u].nc+trie[v].nc+trie[v].ims;
        }
}
void answer(void) {
        int i;
        for (i=1;i<=n;i=i+1) printf("%d\n",trie[id[i]].np+trie[id[i]].nc+trie[id[i]].ims);
}
int main(void) {
        init();
        visit(0);
        answer();
        return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
using namespace std;

struct Node {
    Node * next[2];
    int counter, f;
    Node() { next[0] = next[1] = NULL; counter = f = 0; }   
};

Node * root;

int dfs(Node * root) {
    if(root==NULL) return 0;
    root->f = dfs(root->next[0]) + dfs(root->next[1]);
    return root->f + root->counter;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    root = new Node();
    for(int k=0;k<n;++k) {
        int l, x;
        Node * p = root;
        scanf("%d", &l);
        for(int i=0;i<l;++i) {
            scanf("%d", &x);
            if(p->next[x] == NULL) p->next[x] = new Node();
            p = p->next[x];
        }
        p->counter ++ ;
    }   
    dfs(root);
    for(int k=0;k<m;++k) {
        int l, x;
        Node * p = root;
        scanf("%d", &l);
        int dem = 0, i;
        for(i=0;i<l;++i) {
            scanf("%d", &x);
            if(p->next[x]==NULL) {
                for(int j=i+1;j<l;++j) scanf("%d", &x);
                break;
            }
            p = p->next[x];
            dem += p->counter;
        }
        if(i==l) dem += p->f;
        printf("%d\n", dem);
    }   
    return 0;
}