Pagini recente » Cod sursa (job #501591) | Cod sursa (job #640353) | Cod sursa (job #978583) | Cod sursa (job #3343733) | Cod sursa (job #3348959)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long mod1=1000000007;
const long long mod2=1000000009;
const long long baza=911382323;
/*
Rabin-Karp:
facem hash pentru pattern si pentru fiecare fereastra din text
de aceeasi lungime.
Daca hash-urile sunt egale, avem match posibil.
Cand mutam fereastra cu o pozitie:
- scoatem primul caracter din hash
- inmultim cu baza
- adaugam noul caracter
Astfel obtinem hash-ul noii ferestre in O(1),
deci tot algoritmul devine O(n).
*/
int main()
{
string a, b;
fin>>a>>b;
int n=a.size();
int m=b.size();
if (n>m)
{
fout<<0;
return 0;
}
long long hashA1=0, hashA2=0, hashB1=0, hashB2=0;
long long pow1=1, pow2=1;
for (int i=0; i<n; i++)
{
hashA1=(hashA1*baza+a[i])%mod1;
hashA2=(hashA2*baza+a[i])%mod2;
hashB1=(hashB1*baza+b[i])%mod1;
hashB2=(hashB2*baza+b[i])%mod2;
if (i<n-1)
{
pow1=pow1*baza%mod1;
pow2=pow2*baza%mod2;
}
}
vector<int> rez;
int cnt=0;
if (hashA1==hashB1 and hashA2==hashB2)
{
cnt++;
rez.push_back(0);
}
for (int i=n; i<m; i++)
{
hashB1=(hashB1-b[i-n]*pow1%mod1+mod1)%mod1;
hashB1=hashB1*baza%mod1;
hashB1=(hashB1+b[i])%mod1;
hashB2=(hashB2-b[i-n]*pow2%mod2+mod2)%mod2;
hashB2=hashB2*baza%mod2;
hashB2=(hashB2+b[i])%mod2;
if (hashA1==hashB1 and hashA2==hashB2)
{
cnt++;
if (rez.size()<1000)
{
rez.push_back(i-n+1);
}
}
}
fout<<cnt<<'\n';
for (auto u:rez)
{
fout<<u<<" ";
}
return 0;
}