Pagini recente » Cod sursa (job #3311464) | Cod sursa (job #3323826) | Cod sursa (job #324851) | Cod sursa (job #3324150) | Cod sursa (job #3333590)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long mod=1e9+7;
int base=65 ;
long long h=0;
char smic[2000000];
char smare[2000000];
long long H=0;
long long hash1=0;
char v[2000001];
int cnt=0;
int main()
{
fin.getline(smic,2000000);
fin.getline(smare,2000000);
for(int i=0; i<strlen(smic); i++)
{
H=(H*base+(smic[i]))%mod;
}
long long NMIC=strlen(smic);
long long power=1;
long long NMARE=strlen(smare);
for(int i=0; i<NMIC; i++)
{
hash1=(hash1*base+smare[i])%mod;
if(i!=0)
{
power=(power*base)%mod;
}
}
if(hash1==H)
{
v[cnt++]=0;
}
for(int i=NMIC;i<=NMARE; i++)
{
hash1=((hash1-(smare[i-NMIC]*power)%mod+mod)*base+smare[i])%mod;
if(hash1==H)
{
v[ i - NMIC + 1 ] = 1, cnt++;
}
}
fout<<cnt<<'\n';
cnt=0;
for(int i = 0; i <NMARE and cnt<1000; i++)
{
if(v[i])
{
cnt++;
fout<<i<<' ';
}
}
fout<<'\n';
return 0;
}