Pagini recente » Diferente pentru problema/revolve intre reviziile 23 si 24 | Borderou de evaluare (job #1253714) | Cod sursa (job #1785224) | Cod sursa (job #3304367) | Cod sursa (job #3333581)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
long long mod=1e9+7;
int base=31;
long long h=0;
char smic[2000000];
char smare[2000000];
long long H=0;
long long hash1=0;
long long v[2000000];
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;
}
int NMIC=strlen(smic);
int power=1;
for(int i=0;i<NMIC;i++)
{
hash1=(hash1*base+smare[i])%mod;
if(i!=0)
{
power=(power*base)%mod;
}
}
if(hash1==H)
{
bool ok=true;
for(int j=0;j<NMIC;j++)
{
if(smic[j]!=smare[j]) ok=false;
}
if(ok==true)
{
v[cnt++]=0;
}
}
for(int i=NMIC;smare[i]!='\0';i++)
{
hash1=(((hash1-((smare[i-NMIC])*power)%mod)*base+mod)%mod+smare[i])%mod;
if(hash1==H)
{
bool ok=true;
for(int j=0;j<NMIC;j++)
{
if(smic[j]!=smare[j+i-NMIC+1]) ok=false;
}
if(ok==true)
{
v[cnt]=i-NMIC+1;
cnt++;
}
}
}
fout<<cnt<<'\n';
for(int i = 0; i < min(cnt, 1000); i++)
fout << v[i] << " ";
return 0;
}