Pagini recente » Cod sursa (job #1473363) | Cod sursa (job #1981353) | Cod sursa (job #331844) | Monitorul de evaluare | Cod sursa (job #3232172)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
long long v1,v2,na,nb,h1,h2,p1,p2,m1,m2,i,sol[10005],nr,k;
char a[2000050],b[2000050];
int main()
{
in.getline(a,2000050);
in.getline(b,2000050);
na=strlen(a),nb=strlen(b);
p1=p2=1;
v1=v2=0;
h1=h2=0;
m1=666013;
m2=10003;
for(i=0;i<na;i++)
{
h1=(h1*101+a[i])%m1;
h2=(h2*101+a[i])%m2;
if(i!=0) p1=(p1*101)%m1,
p2=(p2*101)%m2;
v1=(v1*101+b[i])%m1;
v2=(v2*101+b[i])%m2;
}
for(i=na;i<nb;++i){
v1=((v1-(b[i-na]*p1)%m1+m1)*101+b[i])%m1;
v2=((v2-(b[i-na]*p2)%m2+m2)*101+b[i])%m2;
if(v1==h1 && v2==h2) {nr++; if(k<=999)sol[++k]=i-na+1;}
}
out<<nr<<endl;
for(i=1;i<=k;i++)
{
out<<sol[i]<<' ';
}
return 0;
}