Cô cho em bài làm qua tết như sau. Anh chị nào xem giúp em với.
Tìm chuỗi:
Cho một xâu S và một xâu T chỉ gồm các ký tự thường và hoa từ ‘a’ tới ‘z’ và các số từ ‘0’ tới ‘9’. Viết chương trình cho biết xâu T có phải là xâu con (liên tục) của S hay không. Nếu là xâu con thì cho biết vị trí đầu tiên bắt đầu xuất hiện xâu T trong S.
Input: BAI1.INP
Gồm 2 dòng:
Dòng 1: xâu S có độ dài tối đa m, với 0 < m <= 10^6.
Dòng 2: xâu T có độ dài tối đa n, với 0 < n <= 10^6.
Output: BAI1.OUT
Nếu xâu T không phải là xâu con của S thì ghi -1. Ngược lại thì ghi ra chỉ số của vị trí bắt đầu của xâu T ở trong S.
Ví dụ:
Em đã làm rồi mà không biết có trường hợp nào ct sai không. Ngoài ra, ai chỉ giúp em làm sao làm cho nó nhanh hơn. Em thấy nó chạy khá chậm. Chiều dài chuỗi lớn hơn 10000 là phần nâng cao mà ct em chạy không nổi.
Tìm chuỗi:
Cho một xâu S và một xâu T chỉ gồm các ký tự thường và hoa từ ‘a’ tới ‘z’ và các số từ ‘0’ tới ‘9’. Viết chương trình cho biết xâu T có phải là xâu con (liên tục) của S hay không. Nếu là xâu con thì cho biết vị trí đầu tiên bắt đầu xuất hiện xâu T trong S.
Input: BAI1.INP
Gồm 2 dòng:
Dòng 1: xâu S có độ dài tối đa m, với 0 < m <= 10^6.
Dòng 2: xâu T có độ dài tối đa n, với 0 < n <= 10^6.
Output: BAI1.OUT
Nếu xâu T không phải là xâu con của S thì ghi -1. Ngược lại thì ghi ra chỉ số của vị trí bắt đầu của xâu T ở trong S.
Ví dụ:
BAI1.INP | BAI1.OUT |
tettetdenroi et | 2 |
tetabcaabbcy bcaat | -1 |
Em đã làm rồi mà không biết có trường hợp nào ct sai không. Ngoài ra, ai chỉ giúp em làm sao làm cho nó nhanh hơn. Em thấy nó chạy khá chậm. Chiều dài chuỗi lớn hơn 10000 là phần nâng cao mà ct em chạy không nổi.
Mã:
var s,t : ansistring;
i,j,vi_tri : longint;
tim_duoc : boolean;
fi,fo : text;
begin
assign(fi, 'BAI1.INP');
reset(fi);
readln(fi, s);
readln(fi, t);
close(fi);
assign(fo, 'BAI1.OUT');
rewrite(fo);
tim_duoc:=false;
i:=1;
j:=1;
vi_tri:=1;
while (i <= length(s)) do
begin
if (s[i] = t[j]) then
begin
i:=i+1;
j:=j+1;
end
else
begin
j:=1;
i:=i+1;
vi_tri:=i;
end;
if (j > length(t)) then
begin
tim_duoc:=true;
writeln(fo, vi_tri);
break;
end;
end;
if (tim_duoc = false) then
writeln(fo, -1);
close(fo);
end.