Pagini recente » Cod sursa (job #631923) | Cod sursa (job #545590) | Cod sursa (job #1375905) | Cod sursa (job #167492) | Cod sursa (job #2791102)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char unu[2000001],doi[2000001];
long long a[1001];
int nr,l1,l2;
struct h{
long long hvalue=0,m=319993,n=37,pow=1;
h(int nn,int nm){n=nn;m=nm;}
void init(char s[], int len){
pow=1;hvalue=0;
for(int i=len-1;i>=0;i--){
hvalue=(hvalue+(pow*s[i])%m)%m;
if(i)
pow=(pow*n)%m;
}
}
void roll(char toR, char toA){
hvalue=(((hvalue-(toR*pow)%m+m)*n)%m+toA)%m;
}
bool operator==(const h&other) const{
return hvalue==other.hvalue;
}
};
void solve(char s1[],char s2[]){
h shor[2]{{31,319993},{53,40099}};
h lo[2]{{31,319993},{53,40099}};
shor[0].init(s1,l1);
shor[1].init(s1,l1);
lo[0].init(s2,l1);
lo[1].init(s2,l1);
if(shor[0]==lo[0] && shor[1]==lo[1])
a[nr++]=0;
for(int i=l1;i<l2;i++){
lo[0].roll(s2[i-l1],s2[i]);
lo[1].roll(s2[i-l1],s2[i]);
if(lo[0]==shor[0] && lo[1]==shor[1]){
if(nr<=1000)
a[nr++]=i-l1+1;
else nr++;
}
}
}
int main()
{
f.getline(unu,2000001);
f.getline(doi,2000001);
l1=strlen(unu);l2=strlen(doi);
solve(unu,doi);
g<<nr<<"\n";
for(int i=0;i<(nr<=1000?nr:1000);i++)
g<<a[i]<<" ";
}