Pagini recente » Cod sursa (job #2744658) | Cod sursa (job #2597616) | Cod sursa (job #381310) | Cod sursa (job #2137904) | Cod sursa (job #2409722)
#include <bits/stdc++.h>
#define DEF 2000010
#define MODO 666013
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int lenA, lenB, hashA, hashB, pow256 = 1, sol;
vector < int > Pos;
char A[DEF], B[DEF];
int create_hash (char a[], int len) {
int _hash = a[0] % MODO;
for (int i = 1; i < len; ++ i) {
_hash = ((1LL * _hash * 256) % MODO + a[i]) % MODO;
}
return _hash;
}
int roll_hash (int _hash, char to_rem, char to_add) {
_hash = (1LL * ((_hash + MODO) - 1LL * to_rem * pow256 % MODO) * 256 + to_add) % MODO;
return _hash;
}
int main () {
fin >> A >> B;
lenA = strlen (A);
lenB = strlen (B);
for (int i = 1; i < lenA; ++ i) {
pow256 = (1LL * pow256 * 256) % MODO;
}
hashA = create_hash (A, lenA);
hashB = create_hash (B, lenA);
for (int i = 0; i < lenB - lenA; ++ i) {
if (hashA == hashB) {
++ sol;
if (sol <= 1000) {
Pos.push_back (i);
}
}
hashB = roll_hash (hashB, B[i], B[i + lenA]);
}
fout << sol << "\n";
for (auto it : Pos) {
fout << it << " ";
}
return 0;
}