Pagini recente » Cod sursa (job #143917) | Cod sursa (job #2307284) | Cod sursa (job #2035055) | Cod sursa (job #563656) | Cod sursa (job #3199705)
#include <bits/stdc++.h>
#define M 1000000013
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000002],b[2000002];
unsigned long long hashA,hashB,p=1,nr,i;
void hashh();
vector<int> v;
int main()
{
f>>a>>b;
hashh();
int n=strlen(a),m=strlen(b);
if(hashA==hashB)
{
nr++;
v.push_back(0);
}
for(i=n;i<m;i++)
{
hashB=((257*(hashB+M-(b[i-n]*p)%M))%M+b[i])%M;
if(hashA==hashB)
{
nr++;
v.push_back(i-n+1);
}
}
g<<nr<<'\n';
int i=0;
if(nr<=1000)
for(i=0;i<nr;i++)
g<<v[i]<<" ";
else
for(i=0;i<1000;i++)
g<<v[i]<" ";
return 0;
}
void hashh()
{
int n=strlen(a),m=strlen(b);
for(i=0;i<n;i++)
{
hashA=((257*hashA)%M+a[i])%M;
if(i!=0)
p=(p*257)%M;
}
for(i=0;i<n;i++)
{
hashB=((257*hashB)%M+b[i])%M;
}
}