Pagini recente » Cod sursa (job #17216) | Cod sursa (job #597074) | Cod sursa (job #1807016) | Cod sursa (job #2916104) | Cod sursa (job #2791094)
#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;
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;
}
}shor,lo;
void solve(char s1[],char s2[]){
shor.init(s1,l1);
lo.init(s2,l1);
if(shor==lo)
a[nr++]=0;
for(int i=l1;i<l2;i++){
lo.roll(s2[i-l1],s2[i]);
if(lo==shor){
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]<<" ";
}