Xâu mẫu



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, xlà 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í vtìm được sẽ là 5 và chiều dài lớn nhất dsẽ 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 xx[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