Pagini recente » Cod sursa (job #1199896) | Cod sursa (job #320795) | Cod sursa (job #2930082) | Cod sursa (job #165858) | Cod sursa (job #2841122)
#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()
{
f>>a>>b;
int n=strlen(a),val=0,m=strlen(b),nou=0,k=0,basel=1,i;
for(i=0;i<n;i++)
{
val=(val*base+(a[i]-'0'))%hash1;
}
for(i=0;i<n;i++)
{
nou=(nou*base+(b[i]-'0'))%hash1;
}
for(i=0;i<n-1;i++)
{
basel=(basel*base)%hash1;
}
if(nou==val)
{
k++;
v.push_back(0);
}
for(i=n;i<m;i++)
{
nou=(nou-(b[i-n]-'0')*basel)%hash1;
if(nou<0)
nou+=hash1;
nou*=base;
nou=nou+b[i]-'0';
nou%=hash1;
if(nou==val)
{
k++;
if(k<1000)
v.push_back(i-n+1);
}
}
g<<k<<'\n';
for(auto it:v)
g<<it<<" ";
return 0;
}