Pagini recente » Cod sursa (job #3000781) | Cod sursa (job #2461816) | Cod sursa (job #1215410) | Cod sursa (job #379180) | Cod sursa (job #785297)
Cod sursa(job #785297)
#include <fstream>
#define MOD1 1000003
#define MOD2 666013
#define SG 73
#define NM 2000010
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
string A,B;
int N,M,i,j;
int HASH1,HASH2,HASHC1,HASHC2;
int P1,P2;
int MATCH[NM];
int main ()
{
getline(f,A);
getline(f,B);
N=A.size();
M=B.size();
P1=P2=1;
for (i=0; i<N; i++)
{
HASH1=(HASH1*SG+A[i])%MOD1;
HASH2=(HASH2*SG+A[i])%MOD2;
if (i>0)
{
P1=(P1*SG)%MOD1;
P2=(P2*SG)%MOD2;
}
}
for (i=0; i<M; i++)
{
if (i>=N)
{
HASHC1=(HASHC1-(B[i-N]*P1)%MOD1+MOD1)%MOD1;
HASHC2=(HASHC2-(B[i-N]*P2)%MOD2+MOD2)%MOD2;
}
HASHC1=(HASHC1*SG+B[i])%MOD1;
HASHC2=(HASHC2*SG+B[i])%MOD2;
if (HASHC1==HASH1 && HASHC2==HASH2)
MATCH[++MATCH[0]]=i-N+1;
}
g << MATCH[0] << '\n';
for (i=1; i<=MATCH[0]; i++)
g << MATCH[i] << ' ';
g << '\n';
f.close();
g.close();
return 0;
}