Pagini recente » Cod sursa (job #2557147) | Cod sursa (job #275963) | Cod sursa (job #1577928) | Cod sursa (job #200115) | Cod sursa (job #1106238)
#include<iostream>
#include<fstream>
#include<cstring>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int MOD = 10007;
const int KEY = 29;
const int MAXN = 20000002;
string word, sentence;
int last, lung, i, hashA, hashB, k, pmax;
bool sol[MAXN];
int main() {
fin >> word;
fin >> sentence;
lung = word.length();
last = sentence.length();
hashA = 0;
pmax = 1;
for(i = 0; i < lung; i++) {
hashA = (hashA * KEY + word[i]) % MOD;
if(i != 0)
pmax = (pmax * KEY) % MOD;
}
for(i = 0; i < lung; i++) {
hashB = (hashB * KEY + sentence[i]) % MOD;
}
k = 0;
if(hashA == hashB) {
sol[0] = 1;
k++;
}
for(i = lung; i < last; i++) {
hashB = ((hashB - (sentence[i - lung] * pmax) % MOD) * KEY + sentence[i]) % MOD;
if(hashB == hashA) {
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;
}