Sáng tạo trong thuật toán và lập trình với ngôn ngữ Pascal và C# - Tập 1 - Chương 4: Tổ chức dữ liệu

t tổ chức hậu tố như sau. 
Hậu tố của một xâu là đoạn cuối của xâu đó. Như vậy một xâu có chiều dài n sẽ có 
n hậu tố. Thí dụ, với xâu mẫu s[1..10] = 'cabxabcdab' ta có 10 hậu tố sau 
đây: 
s[1..10] = 'cabxabcdab' 
s[2..10] = 'abxabcdab' 
s[3..10] = 'bxabcdab' 
s[4..10] = 'xabcdab' 
s[5..10] = 'abcdab' 
s[6..10] = 'bcdab' 
s[7..10] = 'cdab' 
s[8..10] = 'dab' 
s[9..10] = 'ab' 
s[10..10] = 'b' 
Như vậy, hậu tố sau sẽ nhận được từ hậu tố sát trước nó bằng cách bỏ đi kí tự 
đầu tiên. 
Trước hết ta sắp tăng các hậu tố của xâu mẫu s theo trật tự từ điển. Sử dụng một 
mảng chỉ dẫn id, trong đó id[i] trỏ đến vị trí đầu tiên của hậu tố trong xâu mẫu. Cụ thể 
là, nếu id[i] = k thì hậu tố tương ứng sẽ là s[k..n]. Sau khi sắp tăng các hậu tố của xâu 
mẫu s[1..10] = 'cabxabcdab' ta thu được: 
i id[i] Hậu tố Xâu 
1 9 S[9..10] ab 
2 5 S[5..10] abcdab 
3 2 S[2..10] abxabcdab 
4 10 S[10..10] b 
5 6 S[6..10] bcdab 
6 3 S[3..10] bxabcdab 
7 1 S[1..10] cabxabcdab 
8 7 S[7..10] cdab 
 9 8 S[8..10] dab 
10 4 S[4..10] xabcdab 
Sắp tăng theo chỉ dẫn các hậu tố của xâu 
s[1..10] = 'cabxabcdab' 
Việc còn lại là so sánh xâu x với các hậu tố s[i..j] để tìm khúc đầu chung dài nhất 
giữa chúng. Thí dụ, với x[1..4]='abcd' thì khúc đầu chung dài nhất tìm được với 
hậu tố s[5..10] do id[2] trỏ tới. Vị trí v tìm được sẽ là 5 và chiều dài lớn nhất d sẽ là 4. 
Phần chính của chương trình sẽ như sau: 
procedure Run; 
begin 
... 
n:= length(s); 
Sáng tạo trong Thuật toán và Lập trình Tập I 
122 
for i:=1 to n do id[i]:=i; 
IdQuikSort(1,n); 
while not seekeof(f) do 
begin 
 readln(f,x); 
 writeln(g,x); 
 Tim; {xac dinh v và d} 
 writeln(g,v,BL,d); 
end; 
end; 
Để ý rằng với mỗi xâu x, nếu phần tử đầu tiên của x là x[1] không trùng với phần tử 
đầu tiên của hậu tố h thì chiều dài của khúc đầu chung của chúng sẽ bằng 0. Nhờ nhận 
xét này và do dãy các hậu tố đã được sắp tăng nên với mỗi xâu x, trước hết ta gọi hàm 
Binsearch để thực hiện tìm kiếm nhị phân phần tử x[1] trong dãy gồm các phần tử 
đầu tiên của các hậu tố, sau đó ta thực hiện việc duyệt tìm. 
procedure Tim; 
var 
 i,Len: integer; 
begin 
v:=BinSearch; d := 0; 
if v=0 then exit; 
Maxlen:=0; 
for i:=v to n do 
begin 
 if s[id[i]]x[1] then exit; 
 Len:=Eqsx(id[i]); 
 if Len > d then 
 begin 
 d:=Len; 
 v:=id[i]; 
 end; 
end; 
end; 
Hàm BinSearch sẽ cho ra chỉ dẫn tới hậu tố h đầu tiên thoả điều kiện h[1] = 
x[1]. 
(*--------------------------------- 
 Tim xuat hien cua x[1]trong day 
 da sap cac hau to 
---------------------------------*) 
function BinSearch:integer; 
var 
 d,c,m: integer; 
begin 
d:=1; 
c:=n; 
repeat 
m:=(d+c) div 2; 
if x[1]>s[id[m]] then d:=m+1 
else c:=m; 
until d=c; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
123 
if x[1]s[id[d]] then Binsearch := -1 
else BinSearch := d; 
end; 
Hàm Eqsx(i) cho ta chiều dài lớn nhất của khúc đầu chung giữa hậu tố s[i..n] và 
xâu x. 
(*--------------------------------- 
 Khuc dau dai nhat giua 
 hau to s[i..n] va x 
---------------------------------*) 
function Eqsx(i:integer): integer; 
var 
 k,m:integer; 
begin 
m:=min(length(x),n-i+1); 
for k:=1 to m do 
 if s[i+k-1]x[k] then 
 begin 
 Eqsx:=k-1; 
 exit; 
 end; 
Eqsx:=m; 
end; 
(* Pascal *) 
(*---------------------- 
 STRINGS: Xau mau 
------------------------*) 
program Strings; 
{$B-} 
uses crt; 
const 
 MN = 255; 
 cd = #0; {ki tu trong} 
 cc = #255; {ki tu cuoi cua bang ma ASCII} 
 BL=#32; {dau cach} 
 fn = 'strings.inp'; {tep vao} 
 gn = 'strings.out'; {tep ra} 
type 
 mb1 = array[0..MN] of integer; 
var 
 f,g: text; 
 s,x: string; {s: xau mau} 
 id: mb1; {chi dan} 
 n: integer; {chieu dai xau mau s} 
 v,d: integer; 
 {v: vi tri xuat hien khuc dau cua x trong xau mau s} 
 {d: maxlen} 
(*------------------------------- 
 min cua 2 phan tu 
--------------------------------*) 
Sáng tạo trong Thuật toán và Lập trình Tập I 
124 
function min(a,b:integer):integer; 
begin 
if a<=b then min:=a 
else min:=b; 
end; 
(*------------------------------- 
Tim xuat hien cua x[1] trong day da sap cac hau to 
-------------------------------*) 
function BinSearch:integer; 
var 
 d,c,m: integer; 
begin 
d:=1; 
c:=n; 
repeat 
m:=(d+c) div 2; 
if x[1]>s[id[m]] then d:=m+1 
else c:=m; 
until d=c; 
if x[1]s[id[d]] then Binsearch:=0 
else BinSearch:=d; 
end; 
(*-------------------------------------- 
 so sanh 2 hau to trong s: 
 s[i..n] va s[j..n] 
---------------------------------------*) 
function sanh(i,j:integer):integer; 
var k:integer; 
begin 
for k:=0 to min(n-i,n-j) do 
if s[i+k]s[j+k] then 
begin 
if s[i+k]<s[j+k] then sanh:=-1 
else sanh:=1; 
exit; 
end; 
if i=j then sanh:=0 
 else if i<j then sanh:=1 
else sanh:=-1; 
end; 
(*------------------------------------- 
 Quick sort cac hau to theo chi dan 
-------------------------------------*) 
procedure IdQuickSort(d,c: integer); 
var i,j,m,t: integer; 
begin 
i:=d; {dau} 
j:=c; {cuoi} 
m:=id[(i+j) div 2]; {phan tu giua} 
while i<=j do 
begin 
Sáng tạo trong Thuật toán và Lập trình Tập I 
125 
 while sanh(id[i],m)<0 do inc(i); 
 while sanh(id[j],m)>0 do dec(j); 
 if (i<=j) then 
 begin 
 t:=id[i]; 
 id[i]:=id[j]; 
 id[j]:=t; 
 inc(i); dec(j); 
 end; 
end; 
if d<j then IdQuickSort(d,j); 
if i<c then IdQuickSort(i,c); 
end; 
(*------------------------------------------ 
 Khuc dau dai nhat giua hau to s[i..n] va x 
-------------------------------------------*) 
function Eqsx(i:integer): integer; 
var k,m:integer; 
begin 
m:=min(length(x),n-i+1); 
for k:=1 to m do 
if s[i+k-1]x[k] then 
begin 
Eqsx:=k-1; 
exit; 
end; 
Eqsx:=m; 
end; 
(*-------------------------------------------- 
Tim vi tri va chieu dai lon nhat 
MaxLen giua cac hau to cua xau mau s va xau x 
---------------------------------------------*) 
procedure Tim; 
var i,Len: integer; 
begin 
v:=BinSearch; 
d:=0; 
if v=0 then exit; 
for i:=v to n do 
begin 
 if s[id[i]]x[1] then exit; 
 Len:=Eqsx(id[i]); 
 if Len > d then 
 begin 
 d:=Len; 
 v:=id[i]; 
 end; 
end; 
end; 
procedure Run; 
Sáng tạo trong Thuật toán và Lập trình Tập I 
126 
var i:integer; 
begin 
assign(f,fn); 
reset(f); 
assign(g,gn); 
rewrite(g); 
readln(f, s); 
writeln(g,s); 
n:= length(s); 
for i:=1 to n do id[i]:=i; 
IdQuickSort(1,n); 
while not seekeof(f) do 
begin 
readln(f,x); 
writeln(g,x); 
Tim; 
writeln(g,v,BL,d); 
end; 
close(f); 
close(g); 
end; 
BEGIN 
Run; 
END. 
Dữ liệu kiểm thử 
STRINGS.INP 
Kết quả dự kiến 
STRINGS.OUT 
cabxabcdab 
abcd 
cdaeh 
cabxabcdab 
abcd 
5 4 
cdaeh 
7 3 
// C# 
using System; 
using System.IO; 
namespace SangTao1 
{ 
 /*------------------------ 
 * Xau mau 
 * ----------------------*/ 
 class Strings 
 { 
 const string fn = "strings.inp"; 
 const string gn = "strings.out"; 
 static string s; // xau mau 
 static string x; // xau can xu ly 
Sáng tạo trong Thuật toán và Lập trình Tập I 
127 
 static int[] id; 
static int v = 0;// vi tri xuat hien khuc dau x trg s 
 static int d = 0;// chieu dai x trong s 
 static int n = 0; // chieu dai xau mau 
 static void Main() 
 { 
 Run(); 
 Test(); 
 Console.ReadLine(); 
 } // Main 
 // Doc lai file gn de kiem tra ket qua 
 static void Test() 
 { 
 Console.WriteLine("\n Kiem tra lai ket qua \n\n"); 
 Console.WriteLine("\n Input: " + 
 File.ReadAllText(fn)); 
 Console.WriteLine("\n Output: " + 
 File.ReadAllText(gn)); 
 } 
 static void Run() 
 { 
 StreamReader f = File.OpenText(fn); 
 StreamWriter g = File.CreateText(gn); 
 // Bo qua cac dong trong dau tien 
 while ((s = (f.ReadLine()).Trim()) == "") ; 
 n = s.Length; // Len xau mau 
 id = new int[n]; 
 // Khoi tri cho index 
 for (int i = 0; i < n; ++i) id[i] = i; 
 IdQSort(0, n - 1); 
 Console.WriteLine(" Xau mau: " + s + "\n\n"); 
 SPrint(); 
 g.WriteLine(s); 
 while ((x = f.ReadLine()) != null) 
 { 
 x = x.Trim(); 
 if (x != "") 
 { 
 Console.WriteLine(x); 
 g.WriteLine(x); 
 Find(); 
 g.WriteLine(v + " " + d); 
 } 
 } 
Sáng tạo trong Thuật toán và Lập trình Tập I 
128 
 f.Close(); g.Close(); 
 } 
 static void Find() 
 { 
 v = BinSearch(x[0]);// hau to co ki tu dau la x[0] 
 d = 0; 
 if (v < 0) return; 
 for (int i = v; i < n; ++i) 
 { 
 int j = id[i]; 
 if (s[j] != x[0]) return; 
 int k = ComLen(x, j); 
 if (d < k) { v = j + 1; d = k;} 
 } 
 } 
 // MaxLen khuc dau cua x va hau to s[j... 
 static int ComLen(string x, int j) 
 { 
 int minlen = Min(x.Length, n - j); 
 for (int i = 0; i < minlen; ++i) 
 if (x[i] != s[j + i]) return i; 
 return minlen; 
 } 
 static int Min(int a, int b) 
 { return (a < b) ? a : b;} 
 static int BinSearch(char c) 
 { 
 int i = 0; 
 int j = n - 1; 
 int m = 0; 
 while (i < j) 
 { 
 m = (i + j) / 2; 
 if (s[id[m]] < c) i = m + 1; 
 else j = m; 
 } 
 return (s[id[i]] == c) ? i : -1; 
 } 
 // Hien thi day duoc sap cac hau to 
 // cua s de kiem tra 
 static void SPrint() 
 { 
 Console.WriteLine("\n Cac hau to sap tang: \n"); 
 for (int i = 0; i < n; ++i) 
 Console.WriteLine(s.Substring(id[i], n - id[i])); 
Sáng tạo trong Thuật toán và Lập trình Tập I 
129 
 } 
 static void IdQSort(int d, int c) 
 { 
 int i = d; 
 int j = c; 
 int m = id[(i + j) / 2]; 
 int t = 0; 
 while (i <= j) 
 { 
 while (Sanh(id[i], m) < 0) ++i; 
 while (Sanh(m, id[j]) < 0) --j; 
 if (i <= j) 
 { 
 t = id[i]; id[i] = id[j]; id[j] = t; 
 ++i; --j; 
 } 
 } 
 if (d < j) IdQSort(d, j); 
 if (i < c) IdQSort(i, c); 
 } 
 static int Sanh(int x, int y) 
 { 
 int ix = 0; 
 int iy = 0; 
 for (int i = 0; i < n; ++i) 
 { 
 ix = (x + i) % n; 
 iy = (y + i) % n; 
 if (s[ix] != s[iy]) 
 return (s[ix] < s[iy]) ? -1 : 1; 
 } 
 return 0; 
 } 
 } // Strings 
} // SangTao1 
CHƢƠNG 5 
PHƢƠNG PHÁP THAM LAM