Pagini recente » Cod sursa (job #1187619) | Cod sursa (job #2723871) | Cod sursa (job #1351392) | Cod sursa (job #524800) | Cod sursa (job #1339359)
#include <iostream>
#include <fstream>
#include <cstring>
using namespace std;
#define MAXN 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021
ifstream in("strmatch.in");
ofstream out("strmatch.out");
char A[MAXN],B[MAXN];
bool match[MAXN];
int nr;
int main()
{
int NA,NB,i,hashA1=0,hash1=0,hashA2=0,hash2=0;
in.getline(A,MAXN);
in.getline(B,MAXN);
NA=strlen(A);
NB=strlen(B);
if(NA>NB)
{
out<<"0\n";
return 0;
}
int P1=1;
int P2=1;
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;
}
}
for(i=0;i<NA;i++)
{
hash1=(hash1*P+B[i])%MOD1;
hash2=(hash2*P+B[i])%MOD2;
}
if(hashA1==hash1&&hashA2==hash2)
match[0]=1,nr++;
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(hashA1==hash1&&hashA2==hash2)
match[i-NA+1]=1,nr++;
}
out<<nr<<"\n";
nr=0;
for(i=0;i<NB&&nr<1000;i++)
if(match[i])
{
nr++;
out<<i<<" ";
}
return 0;
}