Pagini recente » Cod sursa (job #3293601) | Cod sursa (job #3135594) | Cod sursa (job #2588902) | Cod sursa (job #2690603) | Cod sursa (job #2380605)
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
#define NMax 2000010
#define b 128
#define Mod 100003
#define Mod2 100019
int d1, d2;
string A, B;
int m, n;
int hashA1, hashA2;
int hash1, hash2;
vector<int> poz;
void RK();
int main(){
fin >> A >> B;
RK();
}
void RK(){
int i, k;
m = A.size();
n = B.size();
d1 = d2 = 1;
for(i = 0; i < m; i++){
hashA1 = (hashA1 * b + A[i]) % Mod;
hashA2 = (hashA2 * b + A[i]) % Mod2;
hash1 = (hash1 * b + B[i]) % Mod;
hash2 = (hash2 * b + B[i]) % Mod2;
if(i != 0){
d1 = (d1 * b) % Mod;
d2 = (d2 * b) % Mod2;
}
}
if(hashA1 == hash1 && hashA2 == hash2) poz.push_back(0);
for(k = 0; k < n - m; k++){
hash1 = ((hash1 - (d1 * B[k]) % Mod + Mod) * b + B[k + m]) % Mod;
hash2 = ((hash2 - (d2 * B[k]) % Mod2 + Mod2) * b + B[k + m]) % Mod2;
if(hashA1 == hash1 && hashA2 == hash2) poz.push_back(k + 1);
}
fout << poz.size() << '\n';
for(i = 0; i < poz.size() && i < 1000; i++) fout << poz[i] << ' ';
}