Pagini recente » Cod sursa (job #1589635) | Cod sursa (job #2785796) | Cod sursa (job #455913) | Cod sursa (job #2043803) | Cod sursa (job #3224507)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#define NMAX 2000000
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define P 73
#define MOD 100007
char A[NMAX+5], B[NMAX+5];
int la, lb;
int hashA, hashB, nr;
bool match[NMAX+5];
int main() {
fin >> A >> B;
la = strlen(A);
lb = strlen(B);
if (la > lb) {
fout << "0\n";
return 0;
}
int powP = 1;
for (int i = 0; i<la; i++) {
hashA = (hashA*P + A[i])%MOD;
hashB = (hashB*P + B[i])%MOD;
if (i != 0) powP = (powP * P) % MOD;
}
if (hashA == hashB) {
match[0] = 1;
nr++;
}
for (int i = la; i<lb; i++) {
hashB = (((hashB - B[i-la]*powP) % MOD + MOD) * P + B[i]) % MOD;
if (hashA == hashB) {
match[i-la+1] = 1;
nr++;
}
}
fout << nr << "\n";
nr = 0;
for (int i = 0; i<lb && nr < 1000; i++) {
if (match[i]) {
fout << i << " ";
nr++;
}
}
return 0;
}