Pagini recente » Cod sursa (job #605855) | Cod sursa (job #286372) | Cod sursa (job #70140) | Cod sursa (job #1225944) | Cod sursa (job #1527846)
#include <fstream>
#include <iostream>
#include <cstring>
#define M1 100129
#define M2 99923
// pt hashuri - 100129 , 99923
// 257 - ca baza || sau 257
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
char a[2000001], b[2000001];
int hashA,hashB,hashA2,hashB2,nr = 0;
int pozitii[2000000];
int pwr(int baza, int exp, int M) {
int rez = 1, power = baza;
while(exp) {
if(exp & 1) {
rez = (rez*power) % M;
}
power = (power*power)%M;
exp >>=1;
}
return rez;
}
int contor = 0;
int main() {
f.getline(a,2000000,'\n');
f.getline(b,2000000, '\n');
int length_a = strlen(a);
int length_b = strlen(b);
for(int i = 0; i < length_a; i++) {
hashA = (hashA + (int)a[i] * pwr(257,length_a - i - 1,M1));
hashA2 = (hashA2 + (int)a[i] * pwr(257,length_a - i - 1,M2));
}
hashA %= M1;
hashA2 %= M2;
for(int i = 0; i < length_a; i++) {
hashB = (hashB + (int)b[i] * pwr(257,length_a - i - 1,M1));
hashB2 = (hashB2 + (int)b[i] * pwr(257,length_a - i - 1,M2));
}
hashB = hashB % M1;
hashB2 %= M2;
if(hashA == hashB && hashA2 == hashB2) {
pozitii[contor] = 0;
contor++;
nr++;
}
for(int i = length_a; i < length_b; i++) {
hashB = ((hashB*257 + (int)b[i]) % M1 - (b[i-length_a] * pwr(257,length_a,M1) % M1) + M1) % M1;
hashB2 = ((hashB2*257 + (int)b[i]) % M2 - (b[i-length_a] * pwr(257,length_a,M2) % M2) + M2) % M2;
hashB %= M1;
hashB2 %= M2;
if(hashA == hashB && hashA2 == hashB2) {
nr++;
pozitii[contor++] = i-length_a + 1;
}
}
g << nr << "\n";
if(nr < 1000)
for(int j = 0; j < nr; j++) {
g << pozitii[j] << " ";
}
else {
for(int j = 0; j < 1000; j++) {
g << pozitii[j] << " ";
}
}
}