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
2018-04-29 10:23:50


Last edit: 2018-04-29 10:25:03
2018-01-09 06:16:59
ez
2017-09-21 15:54:11


THAM KHẢO THUẬT TOÁN VÀ CODE TẠI:

http://yeulaptrinh.pw/319/substr-spoj/


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 làm :v
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.