Pagini recente » Cod sursa (job #3247506) | Cod sursa (job #2274302) | Cod sursa (job #460617) | Cod sursa (job #2258740) | Cod sursa (job #2903498)
#include <bits/stdc++.h>
#define MOD 100003
#define baza 257
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long int h1, h2;
char sir1[2000001];
char sir2[2000001];
vector <int> rasp;
long long int poww(int a, int x);
int main()
{
int x, y, i;
fin.getline(sir1, 2000002);
fin.getline(sir2, 2000002);
h1=0;
x=strlen(sir1);
for(i=0; i<x; i++)
{
h1=(h1*baza+sir1[i])%MOD;
}
h2=0;
y=strlen(sir2);
for(i=0; i<x; i++)
{
h2=(h2*baza+sir2[i])%MOD;
}
if(h1==h2)
{
rasp.push_back(0);
}
for(i=x; i<y; i++)
{
h2=((h2-(sir2[i-x]*poww(baza, x-1))%MOD+MOD)*baza+sir2[i])%MOD;
if(h1==h2)
rasp.push_back(i-x+1);
}
fout<<rasp.size()<<'\n';
for(int i:rasp)
fout<<i<<' ';
return 0;
}
long long int poww(int a, int x)
{
if(x==0)
return 1;
int y=poww(a, x/2);
if(x%2==0)
return (y*y)%MOD;
else
return (y*y*a)%MOD;
}