Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

SUBSTR - Xâu con

Cho xâu A và xâu B chỉ gồm các chữ cái thường. Xâu B được gọi là xuất hiện tại vị trí i của xâu A nếu: A[i] = B[1], A[i+1] = B[2], ..., A[i+length(B)-1] = B[length(B)].

Hãy tìm tất cả các vị trí mà B xuất hiện trong A.

Input

  • Dòng 1: xâu A.
  • Dòng 2: xâu B.
Độ dài A, B không quá 1000000.

Output

Ghi ra các vị trí tìm được trên 1 dòng (thứ tự tăng dần). Nếu B không xuất hiện trong A thì bỏ trắng.

Example

Input:
aaaaa
aa

Output:
1 2 3 4

Được gửi lên bởi:Nguyen Dinh Tu
Ngày:2006-10-11
Thời gian chạy:0.451s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ERL GOSU JS-RHINO NODEJS PERL6 PYPY RUST SED VB.NET

hide comments
2017-03-07 14:54:51
Hash, KMP and Z=>>1 go AC:)))
2017-02-23 07:58:30 Tùng Py
Nice

Last edit: 2017-02-23 08:00:25
2017-02-15 14:23:35
Hash=)) chưa biết làm :v
2017-02-10 15:16:20
Hàm Z AC 0,05s nhé !! ^^!
2016-11-12 04:22:26
{$H+}
Const fi='';
fo='';
nmax=1000000;
Type mang=array[0..nmax] of longint;
Var f:text;
n,m:longint;
a,x:string;
Next:mang;
Procedure Enter;
Var i:longint;
Begin
assign(f,fi);reset(f);
readln(f,a);read(f,x);
close(f);

End;
Procedure Init;
Var j,jj:longint;
Begin

j:=1;jj:=0;
Next[1]:=0;

n:=length(x);m:=length(a);
x:=x+' ';

While j<=n do
begin

While (jj>0) and(x[j]<>x[jj]) do
jj:=Next[jj];

Inc(j);Inc(jj);

If x[j]=x[jj] then
Next[j]:=Next[jj]
Else Next[j]:=jj;

end;
End;

Procedure Print;
Begin
assign(f,fo);
rewrite(f);
End;

Procedure Solve;
Var i,j:longint;
Begin
Init; Print;
i:=1;j:=1;
Repeat
While (j>0) and(x[j]<>a[i]) do
j:=next[j];

Inc(i);Inc(j);

If j>n then
begin
Write(f,i-j+1,' ');
j:=Next[j];
end;

Until i>m;
End;

BEGIN
Enter;
Solve;
Close(f);
END.

2016-09-19 17:19:11
1/ Z -> AC.
2/ KMP -> AC
3/ Hash -> AC
2016-08-26 03:36:49 xin đừng quên tôi
Tham khảo thuật toán và code tại: http://yeulaptrinh.pw/319/substr-spoj/
2016-03-21 07:44:48 atom3296
KMP AC ::)))

Last edit: 2016-03-21 08:29:36
2016-03-19 14:28:50 Phạm Huỳnh Nhật
dùng pos là tle chắc...*thử r ^^*...dùng hash thì mới AC
2016-01-30 14:19:56
Các bạn dùng hàm z như thế nào mà full z??
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.