Pagini recente » Cod sursa (job #493932) | Cod sursa (job #3265720) | Cod sursa (job #1288594) | Cod sursa (job #584936) | Cod sursa (job #2842586)
#include <fstream>
#define BAZA 59
#define NMAX 2000000
#define HASH_CODE_1 666013
#define HASH_CODE_2 1000000007
#define MAXR 1000
#define int long long
using namespace std;
int nrofsol;
int p1, p2;
string sirA;
string sirB;
int sol[MAXR + 1];
signed main(){
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
fin >> sirA; int n = sirA.size();
fin >> sirB; int m = sirB.size();
int pattern1, pattern2, hash1, hash2;
pattern1 = pattern2 = hash1 = hash2 = 0;
p1 = p2 = 1;
for (int i = 0; i < n; i++){
pattern1 = (pattern1 * BAZA + sirA[i]) % HASH_CODE_1;
pattern2 = (pattern2 * BAZA + sirA[i]) % HASH_CODE_2;
hash1 = (hash1 * BAZA + sirB[i]) % HASH_CODE_1;
hash2 = (hash2 * BAZA + sirB[i]) % HASH_CODE_2;
if (i != 0)
p1 = (p1 * BAZA) % HASH_CODE_1, p2 = (p2 * BAZA) % HASH_CODE_2;
}
int parcurg;
parcurg = n;
while (parcurg <= m){
if (hash1 == pattern1 && hash2 == pattern2)
if (nrofsol < MAXR)
sol[nrofsol++] = parcurg - n;
hash1 -= (sirB[parcurg - n] * p1) % HASH_CODE_1;
hash2 -= (sirB[parcurg - n] * p2) % HASH_CODE_2;
if (hash1 < 0)
hash1 += HASH_CODE_1;
if (hash2 < 0)
hash2 += HASH_CODE_2;
hash1 = (hash1 * BAZA + sirB[parcurg]) % HASH_CODE_1;
hash2 = (hash2 * BAZA + sirB[parcurg]) % HASH_CODE_2;
parcurg++;
}
nrofsol = min (nrofsol, MAXR);
fout << nrofsol << "\n";
for (int i = 0; i < nrofsol; i++)
fout << sol[i] << " ";
//for (int i = 0; i < m; i++)
return 0;
}