Pagini recente » Cod sursa (job #2055533) | Cod sursa (job #1103797) | Cod sursa (job #653334) | Cod sursa (job #1992370) | Cod sursa (job #2338503)
#include <fstream>
#include <string.h>
using namespace std;
ifstream in("strmatch.in");
ofstream out("strmatch.out");
const int N=2000001;
const int p=73;
const int MOD1=100007;
const int MOD2=100021;
char A[N],B[N];
int na,nb,p1=1,p2=1,hashA1,hashA2,cnt;
bool match[N];
int main()
{
in>>A;
in>>B;
na=strlen(A);
nb=strlen(B);
hashA1=hashA2=A[0];
int hash1,hash2;
hash1=hash2=B[0];
for(int i=1;i<na;i++)
{
hashA1=(hashA1*p+A[i])%MOD1;
hashA2=(hashA2*p+A[i])%MOD2;
hash1=(hash1*p+B[i])%MOD1;
hash2=(hash2*p+B[i])%MOD2;
p1=(p*p1)%MOD1;
p2=(p*p2)%MOD2;
}
if(na>nb)
{
out<<0;
return 0;
}
for(int i=na;i<=nb;i++)
{
if(hash1==hashA1 && hash2==hashA2)
{
cnt++;
match[i-na]=true;
}
hash1=((hash1-(p1*B[i-na])%MOD1+MOD1)*p+B[i])%MOD1;
hash2=((hash2-(p2*B[i-na])%MOD2+MOD2)*p+B[i])%MOD2;
}
out<<cnt<<'\n';
for(int i=0;i<nb-na+1;i++)
if(match[i])
out<<i<<' ';
return 0;
}