Pagini recente » Cod sursa (job #1929255) | Cod sursa (job #963848) | Cod sursa (job #1166561) | Cod sursa (job #1965501) | Cod sursa (job #2750239)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define MOD1 1000003
#define LMAX 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int sumP[LMAX + 1];
char a[LMAX + 1], b[LMAX + 1];
vector <int> aparitii;
int putere(int b, int e, int MOD){
if(e == 0){
return 1;
}
if(e % 2 == 0){
return putere(1LL * b * b % MOD, e / 2, MOD);
}
return 1LL * b * putere(1LL * b * b % MOD, e / 2, MOD) % MOD;
}
int main()
{
fin.getline(a, LMAX + 1);
fin.getline(b, LMAX + 1);
int lgA = strlen(a);
int lgB = strlen(b);
//calculez Hash
int Hash = 0;
for(int i = 0; i < lgA; i++){
Hash = ( Hash * 27 + a[i] - 'A' + 1 ) % MOD1;
}
sumP[0] = (b[0] - 'A' + 1) % MOD1;
for(int i = 1; i < lgB; i++){
sumP[i] = (sumP[i - 1] * 27 + b[i] - 'A' + 1) % MOD1;
}
/*
cout << "Hash = " << Hash << "\n";
for(int i = 0; i < lgB; i++){
cout << i << " : " << sumP[i] << "\n";
}
cout << "\n";
*/
for(int i = lgA - 1; i < lgB; i++){
//verific daca sirul care se termina in i este subsecventa
int j = i - lgA + 1;
int HashAux;
if(j > 0){
HashAux = ( MOD1 + sumP[i] - ( 1LL * sumP[j - 1] * putere(27, i - j + 1, MOD1) % MOD1 ) ) % MOD1;
}
else {
HashAux = sumP[i];
}
if(HashAux == Hash){
aparitii.push_back(j);
}
/*
cout << j << ' ' << i << "\n";
cout << HashAux << "\n";
cout << "\n";
*/
}
fout << aparitii.size() << "\n";
for(int i = 0; i < aparitii.size(); i++){
fout << aparitii[i] << ' ';
}
return 0;
}