Pagini recente » Cod sursa (job #2228822) | Cod sursa (job #1457665) | Cod sursa (job #3039821) | Cod sursa (job #3148953) | Cod sursa (job #1076286)
#include<fstream>
#include<cstring>
#define maxn 2000005
#define ro1 100007
#define ro2 100021
#define p 97
using namespace std;
ifstream fi("strmatch.in");
ofstream fo("strmatch.out");
char A[maxn],B[maxn];
int hashA1,hashA2;
int hashB1,hashB2;
int na,nb,i,nr=0;
int sol[1005];
int p1,p2;
int main(){
fi>>A;
fi>>B;
na=strlen(A);
nb=strlen(B);
if(na>nb) fo<<"0";
else{
//hashing pentru sirul A
hashA1=hashA2=0;
p1=p2=1;
hashA1=(A[0]+0)%ro1;
hashA2=(A[0]+0)%ro2;
for(i=1;i<na;i++){
hashA1=(hashA1*p+A[i])%ro1;
hashA2=(hashA2*p+A[i])%ro2;
p1=(p1*p)%ro1;
p2=(p2*p)%ro2;
}
//hashing pentru sirul B (primele na caractere)
hashB1=hashB2=0;
for(i=0;i<na;i++){
hashB1=(hashB1*p+B[i])%ro1;
hashB2=(hashB2*p+B[i])%ro2;
}
if(hashA1==hashB1 && hashA2==hashB2) sol[++nr]=0;
//hashing pentru sirul B (urmatoarele caractere)
for(i=na;i<nb;i++)
{
hashB1=( (hashB1 - (B[i-na]*p1)%ro1 + ro1)*p + B[i] )%ro1;
hashB2=( (hashB2 - (B[i-na]*p2)%ro2 + ro2)*p + B[i] )%ro2;
if(nr<1000 && hashA1==hashB1 && hashA2==hashB2) sol[++nr]=i-na+1;
}
fo<<nr<<"\n";
for(i=1;i<=nr;i++) fo<<sol[i]<<" ";
}
fi.close();
fo.close();
return 0;
}