Pagini recente » Cod sursa (job #658776) | Cod sursa (job #2091180) | Cod sursa (job #3126362) | Cod sursa (job #2777338) | Cod sursa (job #1168218)
#include<fstream>
#include<string>
#define Nmax 2000010
using namespace std;
#define P 73
#define MOD1 100007
#define MOD2 100021
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char A[Nmax], B[Nmax];
int i, P1=1, P2=1;
int matches[Nmax], NrM;
int main()
{
fin>>A>>B;
int NA=strlen(A);
int NB=strlen(B);
if(NA>NB)
{
fout<<0<<'\n';
return 0;
}
int hashA1=0, hashA2=0;
for(i=0;i<NA;++i)
{
hashA1=(hashA1*P+A[i])%MOD1;
hashA2=(hashA2*P+A[i])%MOD2;
if(i>0)
P1=(P1*P)%MOD1,
P2=(P2*P)%MOD2;
}
int hash1=0, hash2=0;
for(i=0;i<NA;++i)
{
hash1=(hash1*P+B[i])%MOD1;
hash2=(hash2*P+B[i])%MOD2;
}
if(hash1==hashA1 && hash2==hashA2)
matches[0]=1,
NrM=1;
for(i=NA;i<NB;++i)
{
hash1 = ((hash1 - (B[i - NA] * P1) % MOD1 + MOD1) * P + B[i]) % MOD1;
hash2 = ((hash2 - (B[i - NA] * P2) % MOD2 + MOD2) * P + B[i]) % MOD2;
if(hash1==hashA1 && hash2==hashA2)
matches[i-NA+1]=1,
NrM++;
}
fout<<NrM<<'\n';
NrM=0;
for(i=0;i<NB&&NrM<1000;++i)
if(matches[i])
fout<<i<<' ';
fout<<'\n';
return 0;
}