//
you're reading...
00 - Chủ đề chung, Bài tập huấn luyện, Chủ đề xâu (string)

Bài tập huấn luyện: Knuth-Morris-Pratt text searching

uses crt,Dos;
var
h1,h2,m1,m2,se1,se2,ms1,ms2:word;
b,comparisons:longint;
t,matchfound:array[0..1000000] of longint;
s,f:string;
procedure START;
begin
GETTIME(h1,m1,se1,ms1);
end;

procedure FINISH;
begin
GETTIME(h2,m2,se2,ms2);
writeln;
writeln(‘**************************************************************’);
writeln(‘**************************************************************’);
writeln(‘************************ COMPARISONS : ‘,comparisons:4,’ ******************’);
writeln(‘**************************************************************’);
writeln(‘************************ TEXT LENGTH : ‘,length(f):4,’ ******************’);
writeln(‘**************************************************************’);
writeln(‘***************************** RUNTIME ************************’);
writeln(‘*************************** ‘,((se2-se1)+(m2-m1)*60+(h2-h1)*60*60+(ms2-ms1)/100):0:3,’ SECONDS ********************’);
writeln(‘**************************************************************’);
writeln(‘************** IMPLEMENTATION # 001 – KMP AGLORITHM **********’);
writeln(‘**************************************************************’);
readln;
end;
procedure maketable;
var
x,y:longint;
begin
t[0]:=0; {empty string}
t[1]:=0; {single letter}
x:=1; {match of characters found plus 1}
y:=2; {position in the pattern string starts off as 2}
{since t[0] and t[1] are already set to 0 as default}
while y <= length(s) do
begin
if s[x] = s[y] then
begin {found another match}
t[y]:=x;
inc(x);
inc(y);
end
else
begin
if x <> 0 then
begin {did not find match so trying for a smaller one}
x:=t[x];
end;
if x = 0 then
begin {smallest match found (empty string)}
t[y]:=x;
inc(x);
inc(y);
end;
end;
end;
end;

procedure printtable;
var
aaa:longint;
begin
writeln(‘TABLE : ‘);
for aaa:= 0 to length(s) do
begin
writeln(aaa:4,’ : ‘,t[aaa]:4);
end;
writeln;
end;

procedure findall;
var
x,y:longint;
begin
x:=0; {match so far (empty string)}
y:=1; {position in text (looking for a place to begin the search)}
while y+length(s)-1 <= length(f) do
begin
if s[x+1] = f[y+x] then
begin
while s[x+1] = f[y+x] do
begin
write(upcase(s[x+1]));
inc(comparisons);
inc(x);
if x = length(s) then
begin
inc(b);
matchfound[b]:=y;
break;
end;
end;
writeln;
if x <> length(s) then
writeln(y+x,’ ‘,s[x+1]);
y:=y+x-t[x];
x:=t[x];
inc(comparisons);
x:=0;
inc(y);
end;
end;
end;

procedure printall;
var
aaa:longint;
begin
writeln(‘MATCHES : ‘);
for aaa:= 1 to b do begin
writeln(aaa:4,’ : ‘,matchfound[aaa]:4);
end;
if b = 0 then writeln(‘NONE =P’);
end;
begin
//read in the two strings…the text and the pattern
write(‘TEXT : ‘);
readln(f); {text}
write(‘PATTERN: ‘);
readln(s); {pattern}
writeln;
START;{note start time of program}
maketable;{makes the table}
printtable;{prints the table}
b:=0; {initialize matchfound array}
comparisons:=0;
findall;{finds the matches}
printall;{prints the matches}
FINISH;{note finish time of program and print}
end.

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: