Pagini recente » Cod sursa (job #2105834) | Cod sursa (job #859718) | Cod sursa (job #2248527) | Cod sursa (job #538078) | Cod sursa (job #1535603)
# include <fstream>
# include <iostream>
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
int expo(int baza, int putere, int M)
{
int rez=1, power=baza, exp=putere;
while (exp)
{
if (exp&1)
rez=(1LL*rez*power)%M;
power=(1LL*power*power)%M;
exp>>=1;
}
return rez;
}
char a[2000001], b[2000001], v[1001];
int main()
{
int i=0, la=0, ha1=0, ha2=0, hb1=0, hb2=0, d=0, index=0;
int M1=100129, M2=99923;
f>>a>>b;
for (i=0; a[i]; i++)
{
ha1=(ha1*257+a[i])%M1;
ha2=(ha2*257+a[i])%M2;
la++;
}
for (i=0; i<la; i++)
{
hb1=(hb1*257+b[i])%M1;
hb2=(hb2*257+b[i])%M2;
}
if (ha1==hb1 && ha2==hb2)
{
d++;
v[index]='0';
v[++index]=' ';
index++;
}
for (i=la; b[i]; i++)
{
int put1=expo(257, la, M1)%M1;
int put2=expo(257, la, M2)%M2;
hb1=((hb1*257+b[i])%M1 - (b[i-la]*put1)%M1 + M1)%M1;
hb2=((hb2*257+b[i])%M2 - (b[i-la]*put2)%M2 + M2)%M2;
if (hb1==ha1 && hb2==ha2)
{
d++;
if (d<=1000)
{
v[index]='0'+i-la+1;
v[++index]=' ';
index++;
}
}
}
g<<d<<'\n';
g<<v;
return 0;
}