Pagini recente » Cod sursa (job #2678027) | Cod sursa (job #275679) | Cod sursa (job #1953975) | Cod sursa (job #2950029) | Cod sursa (job #2294356)
#include <iostream>
#include <fstream>
#include <string>
using namespace std;
ifstream si("strmatch.in");
ofstream so("strmatch.out");
#define MAXN 2000005
#define p 73
#define MOD1 100007
#define MOD2 100021
string a, b;
int na, nb;
int hashA1, hashA2, p1, p2;
bool match[MAXN];
int main()
{
si>>a>>b;
na=a.size();
nb=b.size();
p1=p2=1;
hashA1=hashA2=0;
for(int 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;
}
}
if(na>nb) {
so<<0;
return 0;
}
int hash1=0, hash2=0;
for(int i=0; i<na; ++i) {
hash1=(hash1*p+b[i])%MOD1;
hash2=(hash2*p+b[i])%MOD2;
}
int nr=0;
if(hash1==hashA1&&hash2==hashA2) {
match[0]=true;
nr++;
}
for(int 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(hash1==hashA1&&hash2==hashA2) {
match[i-na+1]=1;
++nr;
}
}
so<<nr<<'\n';
nr=0;
for(int i=0; i<nb&&nr<1000; ++i)
if(match[i]) {
nr++;
so<<i<<' ';
}
return 0;
}