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 ladpro98

#include <bits/stdc++.h>
#define ii pair<int, int>
#define X first
#define Y second
const int N = 1010;
using namespace std;

struct STR {
    char str[N];
    int next[N][26];
    int n;
    void Init() {
        n = strlen(str + 1);
        for(int j = 0; j < 26; j++) next[n][j] = 0;
        for(int i = n - 1; i >= 0; i--) 
            for(int j = 0; j < 26; j++)
                if (str[i + 1] - 'a' == j)
                    next[i][j] = i + 1;
                else
                    next[i][j] = next[i + 1][j];
    }
} a, b;
int res;
int d[N][N];
ii Q[N * N];

void BFS() {
    int l = 1, r = 1;
    Q[1] = ii(0, 0);
    while (l <= r) {
        ii u = Q[l++];
        for(int j = 0; j < 26; j++) {
            int x = a.next[u.X][j];
            int y = b.next[u.Y][j];
            if (x == 0) continue;
            if (y == 0) {res = d[u.X][u.Y] + 1; return;}
            if (d[x][y] > 0) continue;
            d[x][y] = d[u.X][u.Y] + 1;
            Q[++r] = ii(x, y);
        }
    }
}

int main() {
    scanf("%s\n", a.str + 1); scanf("%s", b.str + 1);
    a.Init(); b.Init();
    BFS();
    printf("%d", res);
    return 0;
}

Code mẫu của RR

//Written by RR
{$MODE OBJFPC}

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

var
  f1,f2         :       text;
  f             :       array[0..MAXN,0..MAXN] of longint;
  next          :       array[1..MAXN,char] of longint;
  l1,l2         :       longint;
  s1,s2         :       ansistring;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;

procedure closeF;
    begin
      close(f1);
      close(f2);
    end;

procedure inp;
    begin
      readln(f1,s1); l1:=length(s1);
      readln(f1,s2); l2:=length(s2);
    end;

procedure solve;
    var
      i,j,u:longint;
    begin
      for i:=1 to l1 do
        begin
          f[i,1]:=max(f[i-1,1],next[1,s1[i]]);
          for j:=2 to i do
            begin
              u:=f[i-1,j-1]+1;
              f[i,j]:=max(f[i-1,j],next[u,s1[i]]);
            end;
        end;

      for i:=1 to l1 do
        if f[l1,i]>l2 then
          begin
            writeln(f2,i);
            exit;
          end;
    end;

procedure init;
    var
      i,now:longint;
      ch:char;
    begin
      for ch:=#1 to #255 do
        begin
          now:=l2+1; next[l2+1,ch]:=l2+1;
          for i:=l2 downto 1 do
            if s2[i]=ch then
              begin
                next[i,ch]:=i;
                now:=i;
              end
            else next[i,ch]:=now;
        end;
    end;

begin
  openF;
  inp;
  init;
  solve;
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <string.h>
#define max 10000
int n,m,c[1003][30],f[1003][1003];
    char s1[1001],s2[1001];

int min(int a,int b)
{
    if(a<b)
        return a;
    else return b;
}

int main()
{
    //freopen("MSTRING.in","r",stdin);

    scanf("%s %s",s1,s2);
    n = strlen(s1); 
    m = strlen(s2);
    for(int i = 0 ; i<= m+1;i++)
         for(int j = 0; j<=26;j++)
              c[i][j] = m;
    for(int i = m-1;i>=0;i--)
        for(int j = 'a';j<='z';j++)
        {
            if(s2[i] == j)
                c[i][j-'a'] = i;
            else c[i][j-'a'] = c[i+1][j-'a'];
        }
    for(int i=0;i<n+1;i++)
         for(int j=0;j<m+2;j++) f[i][j]=max;
    for(int i = 0;i<n;i++)
    {
        f[i][m+1] = 0;
        f[i][m] = 1;
    }
    for(int i = n-1;i>=0;i--)
        for(int j = m-1;j>=0;j--)
        {
                f[i][j] = min(f[i+1][j],f[i+1][c[j][s1[i]-'a']+1]+1);
        }
    printf("%d",f[0][0]);
    //getch();
}

Code mẫu của ll931110

{$H+}  //String's length is greater than 255
program toki;
const
  input  = '';
  output = '';
  maxn = 1000;
var
  s,t: string;
  F: array[1..maxn,1..maxn] of longint;
  pos: array['a'..'z',0..maxn] of longint;
  num: array['a'..'z'] of longint;
  res: longint;

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

  readln(fi, s);  readln(fi, t);

  close(fi);
end;

procedure enter;
var
  i: longint;
begin
  fillchar(pos, sizeof(pos), 0);
  fillchar(num, sizeof(num), 0);

  for i := 1 to length(t) do
    begin
      inc(num[t[i]]);
      pos[t[i],num[t[i]]] := i;
    end;
end;

procedure dp;
var
  n,i,j,tmp: longint;
  inf,sup,med: longint;
  max: longint;
begin
  fillchar(F, sizeof(F), 0);
  n := length(s);
  for i := 1 to n do
    begin
      F[1,i] := pos[s[i],1];
      if F[1,i] = 0 then
        begin
          res := 1;
          exit;
        end;
    end;

  i := 1;
  repeat
    inc(i);
    max := F[i - 1,i - 1];
    for j := i to n do
      begin
        if pos[s[j],num[s[j]]] <= max then
          begin
            res := i;
            exit;
          end;

        inf := 1;
        sup := num[s[j]];

        repeat
          med := (inf + sup) div 2;
          if pos[s[j],med] <= max then inf := med + 1 else
            begin
              tmp := med;
              sup := med - 1;
            end;
        until inf > sup;

        F[i,j] := pos[s[j],tmp];
        if max < F[i - 1,j] then max := F[i - 1,j];
      end;
  until false;
end;

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

begin
  init;
  enter;
  dp;
  printresult;
end.

Code mẫu của khuc_tuan

//{$A8,B-,C+,D+,E-,F-,G+,H+,I+,J-,K-,L+,M-,N+,O+,P+,Q+,R+,S+,T-,U-,V+,W-,X+,Y+,Z1}
// {$APPTYPE CONSOLE}
 {$mode delphi}

var
    pa, pb : array[0..2000] of char;
    a, b : PChar;
    i, j, na, nb : integer;
    F : array[0..1010,0..1010] of integer;
    prev : array[0..1010,'a'..'z'] of integer;
    pos : array['a'..'z'] of integer;
    c : char;

function getmin(a, b : integer) : integer;
begin
    if a=0 then getmin := b
    else if a < b then getmin := a
        else getmin := b; 
end;

begin
    readln(pa);
    readln(pb);
    a := PChar(@pa);
    Dec(a);
    b := PChar(@pb);
    Dec(b);
    na := Length(PChar(@a[1]));
    nb := Length(PChar(@b[1]));
    for i:=1 to na do
        F[i,0] := 1;
    for i:=1 to nb do
    begin
        pos[b[i]] := i;
        for c:='a' to 'z' do
            prev[i,c] := pos[c];
    end;
    for j:=1 to nb do
    begin
        for i:=1 to na do
        begin
            if F[i-1,j]<>0 then F[i,j] := F[i-1,j];
            if prev[j,a[i]]=0 then F[i,j] := 1
            else if F[i-1,prev[j,a[i]]-1]<>0 then F[i,j] := getmin( F[i,j], F[i-1,prev[j,a[i]]-1] + 1);
        end;
    end;
    writeln( F[na, nb] );
end.