Pagini recente » Cod sursa (job #441699) | Cod sursa (job #2267913) | Cod sursa (job #507069) | Cod sursa (job #2784235) | Cod sursa (job #1106296)
#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 = 97;
const int MAXN = 2000002;
string word, sentence;
int last, lung, i, hashA1, hashB1, k, pmax1;// hashB2, hasA2, pmax2;
bool sol[MAXN];
int main() {
fin >> word;
fin >> sentence;
lung = word.length();
last = sentence.length();
hashA1 = 0;
//hashA2 = 0;
pmax1 = 1;
//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 = 0;
//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) {
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) {
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;
}