SPOJ.com - Problem SUBSTR

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

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/substr

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

Submit solution!

Được gửi lên bởi:	Nguyen Dinh Tu
Ngày:	2006-10-11
Thời gian chạy:	1s
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-09-21 06:29:42
xem code và thuật toán ở
https://vietcodes.github.io/code/80/

2017-08-19 11:21:08 Con Bò Huyền Thoại
https://kienthuc24h.com/substr-spoj-xau-con/

2017-07-25 17:34:24
Z cos vai dong:
#include <bits/stdc++.h>
#define LL long long
#define FORT(i,a,b) for (LL i = (a); i <= (b); ++i)

using namespace std;
LL l,r,z[10000000],n;
string a,b,s;
int main()
{
cin>>a>>b;
s=b+"z"+a;
l=0;
r=0;
n=s.length();
FORT(i,1, n-1)
{
if (i<=r)
z[i]=min(r-i+1,z[i-l]);
while (i+z[i]<n && s[z[i]]==s[i+z[i]])
z[i]++;
if (i+z[i]-1>=r)
{
r=i+z[i]-1;
l=i;
}

if (z[i]==b.length())
cout<<i-b.length()<<" ";
}
return 0;
}

2017-07-24 14:09:16
:D

Last edit: 2018-04-19 02:36:38

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 là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

Giải bài trực tuyến

SUBSTR - Xâu con

Input

Output

Example