Pagini recente » Cod sursa (job #855065) | Cod sursa (job #590692) | Cod sursa (job #851676) | Cod sursa (job #1127409) | Cod sursa (job #3333378)
#include <bits/stdc++.h>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
#define MOD 10000007
int h[2000001];
int pow (int a, int b){
int rez=1;
while (b){
if (b%2==1){///e impar
rez=1ll*a*rez%MOD;
}
a=1ll*a*a%MOD;
b/=2;
}
return rez;
}
int main()
{
int hashA,hashB,p1=1,p2=1,baza=31,inv;
string a,b;
vector<int> poz;
in >> a >> b;
inv=pow(baza,MOD-2);
for (int i=0; i<a.size(); i++){
hashA=(hashA+1ll*a[i]*p1)%MOD;
p1=1ll*p1*baza%MOD;
}
for (int i=0; i<b.size(); i++){
if (i<a.size()){
hashB=(hashB+1ll*b[i]*p2)%MOD;
p2=1ll*p2*baza%MOD;
} else{
hashB=1ll*(hashB-b[i-a.size()]+1ll*b[i]*p2+MOD)*inv%MOD;
}
if (hashA==hashB){
poz.push_back(i-a.size()+1);
}
}
out << poz.size() << '\n';
for (int i=0; i<min(int(poz.size()),1000); i++){
out << poz[i] << " ";
}
return 0;
}