Pagini recente » Cod sursa (job #2829954) | Cod sursa (job #2405847) | Cod sursa (job #917174) | Cod sursa (job #3205720) | Cod sursa (job #2750247)
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>
#define MOD1 1000003
#define MOD2 1000007
#define LMAX 2000000
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
int putere[LMAX + 1];
int sumP[LMAX + 1];
char a[LMAX + 1], b[LMAX + 1];
vector <int> aparitii;
void precalcularePuteri(){
putere[0] = 1;
for(int i = 1; i <= LMAX; i++){
putere[i] = 1LL * putere[i - 1] * 27 % MOD1;
}
}
int main()
{
fin.getline(a, LMAX + 1);
fin.getline(b, LMAX + 1);
int lgA = strlen(a);
int lgB = strlen(b);
precalcularePuteri();
//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 HashAux1;
int HashAux2;
if(j > 0){
HashAux1 = ( MOD1 + sumP[i] - ( 1LL * sumP[j - 1] * putere[i - j + 1] % MOD1 ) ) % MOD1;
HashAux2 = ( MOD2 + sumP[i] - ( 1LL * sumP[j - 1] * putere[i - j + 1] % MOD2 ) ) % MOD2;
}
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;
}