Pagini recente » Cod sursa (job #1534556) | Monitorul de evaluare | Profil M@2Te4i | Statistici Chirtoc Ilinca (ilinca_stefi) | Cod sursa (job #2843500)
#include<bits/stdc++.h>
#define base 75
#define hash1 666013
#define hash2 666007
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000002],b[2000002];
vector<int>v;
int val1=0,val2=0,nou1=0,nou2=0;
int main()
{
f>>a>>b;
int n=strlen(a),m=strlen(b),k=0,basel=1,base2=1,i;
for(i=0;i<n;i++)
{
val1=(val1*base+(a[i]-'0'))%hash1;
val2=(val2*base+(a[i]-'0'))%hash2;
}
for(i=0;i<n;i++)
{
nou1=(nou1*base+(b[i]-'0'))%hash1;
nou2=(nou2*base+(b[i]-'0'))%hash2;
}
for(i=0;i<n-1;i++)
{
basel=(basel*base)%hash1;
base2=(base2*base)%hash2;
}
if(nou1==val1 && nou2==val2)
{
k++;
v.push_back(0);
}
for(i=n;i<m;i++)
{
nou1=(nou1-(b[i-n]-'0')*basel)%hash1;
if(nou1<0)
nou1+=hash1;
nou1*=base;
nou1=nou1+b[i]-'0';
nou1%=hash1;
nou2=(nou2-(b[i-n]-'0')*base2)%hash2;
if(nou2<0)
nou2+=hash2;
nou2*=base;
nou2=nou2+(b[i]-'0');
nou2%=hash2;
if(nou1==val1 && nou2==val2)
{
k++;
if(k<=1000)
v.push_back(i-n+1);
}
}
g<<k<<'\n';
for(auto it:v)
g<<it<<" ";
return 0;
}