Pagini recente » Cod sursa (job #397835) | Cod sursa (job #1198757) | Cod sursa (job #320482) | Cod sursa (job #2563065) | Cod sursa (job #1784299)
#include <fstream>
#include <string.h>
#include <vector>
#define nMax 2000001
#define solMax 1001
#define base 73
#define MOD1 100007
#define MOD2 100021
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int lenA, lenB, nrSol;
int Sol[solMax];
char A[nMax], B[nMax];
void read()
{
fin>>(A+1);
fin>>(B+1);
lenA=strlen(A+1);
lenB=strlen(B+1);
}
void write()
{
fout<<nrSol<<'\n';
for(int i=1; i<=min(1000, nrSol); i++)
fout<<Sol[i]<<" ";
}
void solve()
{
int hash1A=0, hash2A=0, hash1B=0, hash2B=0, base1=1, base2=1;
for(int i=1; i<=lenA; i++)
{
hash1A=(hash1A*base+A[i])%MOD1;
hash2A=(hash2A*base+A[i])%MOD2;
hash1B=(hash1B*base+B[i])%MOD1;
hash2B=(hash2B*base+B[i])%MOD2;
if(i>1)
{
base1=(base1*base)%MOD1;
base2=(base2*base)%MOD2;
}
}
if(hash1A==hash1B && hash2A==hash2B)
{
nrSol++;
if(nrSol<solMax)
Sol[nrSol]=0;
}
for(int i=lenA+1; i<=lenB; i++)
{
hash1B=((hash1B-(base1*B[i-lenA])%MOD1+MOD1)*base+B[i])%MOD1;
hash2B=((hash2B-(base2*B[i-lenA])%MOD2+MOD2)*base+B[i])%MOD2;
if(hash1A==hash1B && hash2A==hash2B)
{
nrSol++;
if(nrSol<solMax)
Sol[nrSol]=i-lenA;
}
}
}
int main()
{
read();
solve();
write();
}