Pagini recente » Cod sursa (job #1262750) | Cod sursa (job #922213) | Cod sursa (job #971722) | Cod sursa (job #1306562) | Cod sursa (job #2841405)
#include<bits/stdc++.h>
#define base 75
#define hash1 666013
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000002],b[2000002];
vector<int>v;
int main()
{
int i,n,m,base1=1,nr1=0,k=0;
f>>a>>b;
n=strlen(a);
m=strlen(b);
int nr=0;
for(i=0;i<n;i++)
{
nr=(nr*base+(a[i]-'0'))%hash1;
}
for(i=0;i<n-1;i++)
base1=(base1*base)%hash1;
for(i=0;i<n;i++)
{
nr1=(nr1*base+(b[i]-'0'))%hash1;
}
if(nr==nr1)
{
k++;
v.push_back(0);
}
for(i=n;i<m;i++)
{
nr1=(nr1-(b[i-n]-'0')*base1)%hash1;
if(nr1<0)
nr1+=hash1;
nr1=(nr1*base);
nr1+=(b[i]-'0');
nr1%=hash1;
if(nr1==nr)
{
k++;
if(k<=1000)
v.push_back(i-n+1);
}
}
g<<k<<'\n';
for(auto it:v)
g<<it<<" ";
return 0;
}