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
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();
}

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.

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.