02/10/2018, 13:58
SUBSTR spoj – Xâu con
Nguồn đề bài: SUBSTR 1. Đề bài SUBSTR spoj 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 ...
Nguồn đề bài: SUBSTR
1. Đề bài SUBSTR spoj
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
2. Code tham khảo HASH, KMP (pascal, c++):
a. HASH C++
#include <iostream>
#include <string>
#include <vector>
using namespace std;
typedef long long int ll;
const ll base=10e8+3;
const int maxn=10e5+1;
string a,b;
vector<ll> Pow,HashA;
int na,nb;
void Init()
{
cin>>a>>b;
na=a.length(); a=" "+a;
nb=b.length(); b=" "+b;
Pow.resize(nb+2);
HashA.resize(na+2);
}
ll getHash(int i)
{
return(HashA[i+nb-1]-HashA[i-1]*Pow[nb]+base*base)%base;
}
void Solve()
{
ll HashB=0;
Pow[0]=1;
for(int i=1;i<=nb;i++)
{
HashB=(HashB*26 + b[i]-'a')%base;
Pow[i]=(Pow[i-1]*26)%base;
}
for(int i=1;i<=na;i++)
HashA[i]=(HashA[i-1]*26+a[i]-'a')%base;
for (int i=1;i<=na-nb+1;i++)
{
if(HashB==getHash(i))
printf("%d ",i);
}
}
int main()
{
Init();
Solve();
}
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 | #include <iostream> #include <string> #include <vector> using namespace std; typedef long long int ll; const ll base=10e8+3; const int maxn=10e5+1; string a,b; vector<ll> Pow,HashA; int na,nb; void Init() { cin>>a>>b; na=a.length(); a=" "+a; nb=b.length(); b=" "+b; Pow.resize(nb+2); HashA.resize(na+2); } ll getHash(int i) { return(HashA[i+nb-1]-HashA[i-1]*Pow[nb]+base*base)%base; } void Solve() { ll HashB=0; Pow[0]=1; for(int i=1;i<=nb;i++) { HashB=(HashB*26 + b[i]-'a')%base; Pow[i]=(Pow[i-1]*26)%base; } for(int i=1;i<=na;i++) HashA[i]=(HashA[i-1]*26+a[i]-'a')%base; for (int i=1;i<=na-nb+1;i++) { if(HashB==getHash(i)) printf("%d ",i); } } int main() { Init(); Solve(); } |
b. Hash pascal
const fi=';
nmax=1000000;
base=1000000007;
type data=longint;
var
f:text;
A,B:Ansistring;
pow,HashA:array[0..nmax+1] of int64;
hashB:int64;
procedure powermod;
var i:data;
begin
pow[0]:=1;
for i:=1 to length(a) do
pow[i]:=(pow[i-1]*26) mod base;
end;
function getHash(i,j:data):data;
begin
gethash:=(HashA[j]-HashA[i-1]*pow[j-i+1]+base*base) mod base;
end;
procedure xuli;
var i,j:data;
begin
hashB:=0;
for i:=1 to length(b) do
Hashb:=(hashb*26+ord(b[i])-48) mod base;
HashA[0]:=0;
for i:=1 to length(a) do
begin
HashA[i]:=(Hasha[i-1]*26+ord(a[i])-48) mod base;
end;
for i:=1 to length(a)-length(b)+1 do
if hashB=gethash(i,i+length(b)-1) then
write(i,' ');
end;
begin
assign(f,fi); reset(f);
readln(f,a);
readln(f,b);
close(f);
Powermod;
xuli;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | const fi='; nmax=1000000; base=1000000007; type data=longint; var f:text; A,B:Ansistring; pow,HashA:array[0..nmax+1] of int64; hashB:int64; procedure powermod; var i:data; begin pow[0]:=1; for i:=1 to length(a) do pow[i]:=(pow[i-1]*26) mod base; end; function getHash(i,j:data):data; begin gethash:=(HashA[j]-HashA[i-1]*pow[j-i+1]+base*base) mod base; end; procedure xuli; var i,j:data; begin hashB:=0; for i:=1 to length(b) do Hashb:=(hashb*26+ord(b[i])-48) mod base; HashA[0]:=0; for i:=1 to length(a) do begin HashA[i]:=(Hasha[i-1]*26+ord(a[i])-48) mod base; end; for i:=1 to length(a)-length(b)+1 do if hashB=gethash(i,i+length(b)-1) then write(i,' '); end; begin assign(f,fi); reset(f); readln(f,a); readln(f,b); close(f); Powermod; xuli; end. |
c. KMP pascal
const fi=';
var f:text;
a,b:ansistring;
T:array[1..1000000] of longint;
i,j:longint;
begin
assign(f,fi); reset(f); readln(f,a); readln(f,b); close(f);
j:=0;
T[1]:=0;
for i:=2 to length(b) do
begin
while (j>0) and (B[i]<>B[j+1]) do
j:=t[j];
if b[i]=b[j+1] then
inc(j);
t[i]:=j;
end;
j:=0;
for i:=1 to length(a) do
begin
while (j>0) and (b[j+1]<>a[i]) do
j:=t[j];
if b[j+1]=a[i] then inc(j);
if j=length(b) then
begin
write(i-j+1,' ');
j:=t[length(b)];
end;
end;
end.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | const fi='; var f:text; a,b:ansistring; T:array[1..1000000] of longint; i,j:longint; begin assign(f,fi); reset(f); readln(f,a); readln(f,b); close(f); j:=0; T[1]:=0; for i:=2 to length(b) do begin while (j>0) and (B[i]<>B[j+1]) do j:=t[j]; if b[i]=b[j+1] then inc(j); t[i]:=j; end; j:=0; for i:=1 to length(a) do begin while (j>0) and (b[j+1]<>a[i]) do j:=t[j]; if b[j+1]=a[i] then inc(j); if j=length(b) then begin write(i-j+1,' '); j:=t[length(b)]; end; end; end. |
