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='';
      fo='';
      maxn=250250;
type ar=array[1..maxn] of ansistring;
var n,re:longint;
    a:ar;
    f,d:array[0..maxn] of longint;

procedure rf;
var i:longint;
begin
     assign(input,fi);
     reset(input);
     readln(n);
     for i:=1 to n do readln(a[i]);
     close(input);
end;

procedure sort(l,r:longint);
var i,j:longint; x,y:ansistring;
begin
     i:=l; j:=r; x:=a[(i+j) div 2];
     repeat
           while a[i]<x do i:=i+1;
           while a[j]>x do j:=j-1;
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                i:=i+1; j:=j-1;
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure pr;
var i,j,l:longint;
begin
     sort(1,n);
     for i:=2 to n do
     begin
          for j:=i-1 downto 1 do
          begin
               if a[i][1]<>a[j][1] then break;
               if pos(a[j],a[i])=1 then
               begin
                    d[i]:=j; break;
               end;
          end;
     end;
     f[1]:=1; re:=1;
     for i:=2 to n do
     begin
          f[i]:=f[d[i]]+1;
          if f[i]>re then re:=f[i];
     end;
end;

procedure wf;
begin
     assign(output,fo);
     rewrite(output);
     write(re);
     close(output);
end;

begin
     rf;
     pr;
     wf;
end.

Code mẫu của happyboy99x

#include<cstdio>
#include<algorithm>
using namespace std;

const int L = 250000 + 5;
int trie[L][26], nnode, f[L], finish[L];
char s[L];

void mark(const char * s) {
    int u = 0;
    for(int i = 0; s[i]; ++i) {
        int t = s[i] - 'a';
        if(trie[u][t] == 0)
            trie[u][t] = ++nnode;
        u = trie[u][t];
    }
    finish[u] = 1;
}

void solve() {
    for(int i = nnode; i >= 0; --i) {
        for(int j = 0; j < 26; ++j)
            if(trie[i][j]) f[i] = max(f[i], f[trie[i][j]]);
        f[i] += finish[i];
    }
    printf("%d\n", f[0]);
}

int main() {
    int m; scanf("%d", &m);
    while(m--) {
        scanf("%s", s);
        mark(s);
    }
    solve();
    return 0;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 250002;
using namespace std;
int n; char s[N];

class Trie {
public:
    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;}
    };
    int ans;
    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;
    }

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

    void DFS(int u, int cnt) {
        if (a[u].e == 1) {
            cnt++; ans = max(ans, cnt);
        }
        for(int i=0; i<26; i++)
        if (a[u][i] != 0)
            DFS(a[u][i], cnt);
    }

    int Find() {
        ans = 0;
        DFS(0, 0);
        return ans;
    }
    Trie() {clear();};
};

Trie T;

int main()
{
    scanf("%d\n", &n);
    for(int i=1; i<=n; i++) {
        gets(s);
        T.Add(s);
    }
    int res = T.Find();
    printf("%d", res);
    return 0;
}

Code mẫu của RR

//Written by RR
{$ifdef rr}
  {$mode objfpc}
  {$r+,q+,h-}
  {$inline off}
{$else}
  {$mode objfpc}
  {$r-,q-,h+}
  {$inline on}
{$endif}

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

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

var
  f1,f2         :       text;
  root          :       trie;
  s             :       string;

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); inline;
    var
      c:char;
    begin
      new(a);
      a^.u:=0;
      a^.f:=0;
      for c:='a' to 'z' do
          a^.c[c]:=nil;
    end;

procedure inp;
    var
      n,i:longint;
      p:trie;
    begin
      readln(f1,n);
      add(root);
      for n:=1 to n do
        begin
          readln(f1,s); p:=root;
          for i:=1 to length(s) do
            begin
              if p^.c[s[i]]=nil then add(p^.c[s[i]]);
              p:=p^.c[s[i]];
            end;
          p^.u:=1;
        end;
    end;

procedure dfs(a:trie); inline;
    var
      c:char;
    begin
      a^.f:=a^.u;
      for c:='a' to 'z' do
        if a^.c[c]<>nil then
          begin
            dfs(a^.c[c]);
            a^.f:=max(a^.f,a^.c[c]^.f+a^.u);
          end;
    end;

procedure solve;
    begin
      dfs(root);
      writeln(f2,root^.f);
    end;

begin
  openF;
  inp;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <algorithm>
#include <bitset>
#include <deque>
#include <iostream>
#include <iomanip>
#include <limits>
#include <list>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef vector <int> vi;
typedef vector <string> vs;


#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 REP(i, a) for (int i = 0; i < (a); i++)
#define REPD(i, a) for (int i = ((a) - 1); i >= 0; i--)
#define FIT(it, v) for (typeof((v).begin())it = (v).begin(); it != (v).end(); ++it)
#define FITD(it, v) for (typeof((v).rbegin())it = (v).rbegin(); it != (v).rend(); ++it)
#define fe(i,a) for(__typeof(a.begin()) i=a.begin();i!=a.end();i++)
#define VAR(a, b) typeof(b) a(b)
#define ALL(v) (v).begin(), (v).end()
#define SET(a, x) memset((a), (x), sizeof(a))
#define SIZE(a) ((int)(a).size())

#define EXIST(a, b) (find(ALL(a), (b)) != (a).end())
#define SORT(x) sort(ALL(x))
#define GSORT(x) sort(ALL(x), greater<typeof(*((x).begin()))>())
#define UNIQUE(v) SORT(v); (v).resize(unique(ALL(v)) - (v).begin())
#define ENUM(v) FIT(it, (v)) cout << *it << " "; cout << endl

#define PF push_front
#define PB push_back
#define MP make_pair
#define F first
#define S second

// bit operater
int BIT(ll x,int i) { return(x&(1<<i));}
ll ONBIT(int i,ll x){ return(x|(1<<i));}
ll OFFBIT(int i,ll x){return (x& ~(1<<i));}
ll FLIPBIT(int i,ll x){return (x^(1<<i));}

const char IN[] = "_.in";
const char OUT[] = "_.out";
const int maxn=255555;

struct vertex
{
    int next[26];   
};
vertex Trie[maxn];
int fx[maxn]; // so leaf da chay qua
int n,now,sz,res=0;
string s[maxn];

void init()
{
    SET(fx,0);
    SET(Trie[0].next,-1);
    sz=1;
}
void add(string a)
{
    int now=0;
    FOR(i,0,a.length()-1)
    {
        int c=a[i]-'a';
        if (Trie[now].next[c]==-1)
        {
            SET(Trie[sz].next,-1);
            fx[sz]=fx[now];
            Trie[now].next[c]=sz;
            sz++;
        }
        res=max(res,fx[now]);
        now=Trie[now].next[c];
    }
    fx[now]++;
    res=max(res,fx[now]);
}
int main() {
  //freopen(IN, "r", stdin);
//  freopen(OUT, "w", stdout);  
    cin>>n;
    FOR(i,1,n) cin>>s[i];
    sort(s+1,s+n+1);
    init();
    FOR(i,1,n) add(s[i]);
    cout<<res;

}

Code mẫu của ll931110

{$MODE DELPHI,H+}
program CHAIN2;
const
  input  = '';
  output = '';
type
  ptree = ^ttree;
  ttree = record
    val: integer;
    q: array['a'..'z'] of ptree;
  end;
var
  root: ptree;
  n,max: integer;

procedure Trie;
var
  f: text;
  i,j: integer;
  ch: char;
  s: string;
  p,t: ptree;
begin
  assign(f, input);
    reset(f);

  new(root);
  root^.val := 0;
  for ch := 'a' to 'z' do root^.q[ch] := nil;

  readln(f, n);
  for i := 1 to n do
    begin
      readln(f, s);
      p := root;

      for j := 1 to length(s) do
        begin
          t := p^.q[s[j]];
          if t = nil then
            begin
              new(t);
              t^.val := 0;
              for ch := 'a' to 'z' do t^.q[ch] := nil;
              p^.q[s[j]] := t;
            end;
          p := t;
        end;

      p^.val := 1;
    end;

  close(f);

  max := 1;
end;

procedure calc(p: ptree);
var
  ch: char;
  t: ptree;
begin
  for ch := 'a' to 'z' do
    begin
      t := p^.q[ch];
      if t <> nil then
        begin
          t^.val := t^.val + p^.val;
          if max < t^.val then max := t^.val;
          calc(t);
        end;
    end;
end;

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

begin
  Trie;
  calc(root);
  printresult;
end.

Code mẫu của skyvn97

#include<bits/stdc++.h>
#define MAX   250052
#define LET   27
using namespace std;
struct nod {
    int pa;
    int ch[LET];
    bool isw;
    int cnt;
    nod(){}
    nod(const int &_pa) {
        pa=_pa;
        int i;
        for (i='a';i<='z';i=i+1) ch[i-'a']=-1;
        isw=false;
        cnt=0;
    }
};
vector<nod> trie;
int n,res;
int id[MAX];
char s[MAX];
void insert(const int &i,const char &c) {
    trie.push_back(nod(i));
    trie[i].ch[c-'a']=trie.size()-1;
}
void maximize(int &x,const int &y) {
    if (x<y) x=y;
}
void init(void) {
    trie.clear();
    trie.push_back(nod(-1));
    scanf("%d",&n);
    int i,j,l,u;
    for (i=1;i<=n;i=i+1) {
        scanf("%s",s);
        l=strlen(s);
        u=0;
        for (j=0;j<l;j=j+1) {
            if (trie[u].ch[s[j]-'a']<0) insert(u,s[j]);
            u=trie[u].ch[s[j]-'a'];
        }
        trie[u].isw++;
        id[i]=u;
    }   
}
void visit(const int &u) {
    int i,v;
    for (i='a';i<='z';i=i+1) {
        v=trie[u].ch[i-'a'];
        if (v<0) continue;
        trie[v].cnt=trie[u].cnt+trie[v].isw;
        maximize(res,trie[v].cnt);
        visit(v);
    }
}
void process(void) {
    res=-1;
    visit(0);
    printf("%d",res);
}
int main(void) {
    init();
    process();
    return 0;
}

Code mẫu của khuc_tuan

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <sstream>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

using namespace std;

#define Rep(i,n) for(int i=0,lll=(n);i<lll;++i)
#define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i)
#define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i)
#define pb push_back
#define MP make_pair
#define fi first
#define se second
#define nextint __nextint()

inline int __nextint() { int x; scanf("%d", &x); return x; }

const int MAXN = 250050;

char buf[MAXN];
char *a[MAXN];
int n;
int L[MAXN], F[MAXN];

bool cmp(char * a, char * b) {
    return strcmp(a,b) < 0;
}

bool check(char *a, char *b) {
    for(int i=0;a[i]!=0 && b[i]!=0;++i) {
        if(a[i]!=b[i]) return false;
    }
    return true;
}

int main() {
    scanf("%d", &n);
    gets(buf);
    Rep(i,n) {
        gets(buf);
        int ls = strlen(buf);
        a[i] = new char[ls + 1];
        memmove( a[i], buf, ls + 1);
    }
    sort( a, a + n, cmp);
    // Rep(i,n) printf("%s\n", a[i]);
    Rep(i,n) {
        int j = i - 1;
        while(j >= 0 && !check(a[j], a[i])) j = L[j];
        L[i] = j;
    }
    int best = 0;
    Rep(i,n) {
        if(L[i] == -1) F[i] = 1;
        else
            F[i] = F[L[i]] + 1;
        best >?= F[i];
    }
    printf("%d\n", best);
    return 0;
}