Pagini recente » Cod sursa (job #2586695) | Cod sursa (job #668925) | Cod sursa (job #126285) | Cod sursa (job #536772) | Cod sursa (job #2750253)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define MIN 48
#define BAZA 76 // 'z' - '0' + 1 + 1 = 75 + 1 = 76
#define LMAX 2000000
#define MOD1 1000003
#define MOD2 1000007
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
char a[LMAX + 1], b[LMAX + 1];
vector <int> aparitii;
int main()
{
fin.getline(a, LMAX + 1);
fin.getline(b, LMAX + 1);
int lgA = strlen(a);
int lgB = strlen(b);
if(lgA > lgB){
fout << 0;
return 0;
}
int hashA1 = 0;
int hashA2 = 0;
for(int i = 0; i < lgA; i++){
hashA1 = (hashA1 * BAZA + a[i] - MIN + 1 ) % MOD1;
hashA2 = (hashA2 * BAZA + a[i] - MIN + 1 ) % MOD2;
}
int P1 = 1;
int P2 = 1;
for(int i = 1; i <= lgA - 1; i++){
P1 = P1 * BAZA % MOD1;
P2 = P2 * BAZA % MOD2;
}
int hash1 = 0;
int hash2 = 0;
for(int i = 0; i < lgA; i++){
hash1 = (hash1 * BAZA + b[i] - MIN + 1) % MOD1;
hash2 = (hash2 * BAZA + b[i] - MIN + 1) % MOD2;
}
if(hash1 == hashA1 && hash2 == hashA2){
aparitii.push_back(0);
}
for(int i = lgA; i < lgB; i++){
//sirul care se termina in i
//acum il adaug pe i si il sterg pe j
int j = i - lgA;
hash1 = ( (MOD1 + hash1 - 1LL * (b[j] - MIN + 1) * P1 % MOD1) % MOD1 * BAZA + (b[i] - MIN + 1) ) % MOD1;
hash2 = ( (MOD2 + hash2 - 1LL * (b[j] - MIN + 1) * P2 % MOD2) % MOD2 * BAZA + (b[i] - MIN + 1) ) % MOD2;
/*
cout << i << "\n";
cout << "hash1 = " << hash1 << "\n";
cout << "hash2 = " << hash2 << "\n";
*/
if(hash1 == hashA1 && hash2 == hashA2){
aparitii.push_back(j + 1);
}
}
fout << aparitii.size() << "\n";
for(int i = 0; i < aparitii.size(); i++){
fout << aparitii[i] << ' ';
}
return 0;
}