Xâu mẫu - gia sư tin học
Một
tệp văn bản f có tên STRINGS.INP chứa các xâu kí tự, mỗi dòng ghi một xâu có
chiều dài tối đa 250 kí tự. Xâu đầu tiên được gọi là xâu mẫu s. Lập trình:
Đọc
xâu mẫu s từ tệp f, ghi vào tệp văn bản g có tên STRINGS.OUT. Sau đó đọc từng
xâu x còn lại của f, với mỗi xâu x cần ghi vào g các thông tin sau:
-
nội dung xâu x;
-
hai số v và d cách nhau
qua dấu cách, trong đó v là vị trí xuất hiện
và d là chiều dài lớn nhất của khúc đầu của x trong xâu mẫu s. Nếu vô
nghiệm thì ghi -1 0.
Thí dụ:
|
STRINGS.INP
|
STRINGS.OUT
|
|
cabxabcdab
abcd
cdaeh
|
cabxabcdab
abcd
5 4
cdaeh
7 3
|
Thuật toán
Với mỗi xâu kí tự w ta kí
hiệu w[i..j], i £ j, và gọi
là đoạn, là xâu gồm dãy kí tự liên tiếp từ w[i] đến w[j] trong xâu w. Thí dụ, nếu w = 'cabxabcdab' thì w[5..8] = 'abcd'. Gọi s là xâu mẫu, x
là xâu cần khảo sát. Nhiệm vụ của ta là tìm vị trí v và chiều dài lớn nhất d để
x[1..d] = s[v..(v
+ d – 1)]. Ta vận dụng kĩ thuậ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);
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;
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
--------------------------------*)
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
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;
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
|
Không có nhận xét nào:
Đăng nhận xét