Pagini recente » Cod sursa (job #2776069) | Cod sursa (job #3177064) | Cod sursa (job #61740) | ONIS 2015, Solutii Runda 1 | Cod sursa (job #1106299)
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD1 = 20323;
const int MOD2 = 20233;
const int KEY = 73;
const int MAXN = 2000002;
string word, sentence;
int last, lung, i, hashA1, hashA2, hashB1, hashB2, k, pmax1, pmax2;
bool sol[MAXN];
int main() {
fin >> word;
fin >> sentence;
lung = word.length();
last = sentence.length();
hashA1 = hashA2 = 0;
pmax1 = pmax2 = 1;
for(i = 0; i < lung; i++) {
hashA1 = (hashA1 * KEY + word[i]) % MOD1;
hashA2 = (hashA2 * KEY + word[i]) % MOD2;
if(i != 0) {
pmax1 = (pmax1 * KEY) % MOD1;
pmax2 = (pmax2 * KEY) % MOD2;
}
}
hashB1 = hashB2 = 0;
for(i = 0; i < lung; i++) {
hashB1 = (hashB1 * KEY + sentence[i]) % MOD1;
hashB2 = (hashB2 * KEY + sentence[i]) % MOD2;
}
k = 0;
if((hashA1 == hashB1) && (hashA2 == hashB2)) {
sol[0] = 1;
k++;
}
for(i = lung; i < last; i++) {
hashB1 = ((hashB1 - (sentence[i - lung] * pmax1) % MOD1 + MOD1) * KEY + sentence[i]) % MOD1;
hashB2 = ((hashB2 - (sentence[i - lung] * pmax2) % MOD2 + MOD2) * KEY + sentence[i]) % MOD2;
if((hashB1 == hashA1) && (hashB2 == hashA2)) {
sol[i - lung + 1] = 1;
k++;
}
}
fout << k << '\n';
k = 0;
for(i = 0; i < MAXN && k < 1000; i++) {
if(sol[i]) {
fout << i << ' ';
k++;
}
}
fin.close();
fout.close();
return 0;
}