Pagini recente » Cod sursa (job #2274201) | Cod sursa (job #1390314) | Cod sursa (job #1113436) | Cod sursa (job #287619) | Cod sursa (job #1166646)
#include<iostream>
#include<fstream>
#include<cstring>
#include<queue>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int KEY = 73;
const int MOD1 = 20233;
const int MOD2 = 20323;
int n, l, L, i, p1, p2, hashA1, hashA2, hashB1, hashB2, k;
string sent, word;
queue<int> sol;
int main() {
getline(fin, word);
getline(fin, sent);
l = word.length();
L = sent.length();
p1 = 1;
p2 = 1;
for(i = 0; i < l; i++) {
hashA1 = (((hashA1 * KEY) % MOD1) + word[i]) % MOD1;
hashA2 = (((hashA2 * KEY) % MOD2) + word[i]) % MOD2;
if(i != 0) {
p1 = (p1 * KEY) % MOD1;
p2 = (p2 * KEY) % MOD2;
}
}
for(i = 0; i < l; i++) {
hashB1 = (((hashB1 * KEY) % MOD1) + sent[i]) % MOD1;
hashB2 = (((hashB2 * KEY) % MOD2) + sent[i]) % MOD2;
}
if((hashA1 == hashB1) && (hashA2 == hashB2)) {
sol.push(0);
}
for(i = l; i < L; i++) {
hashB1 = ((((hashB1 - ((sent[i-l] * p1) % MOD1) + MOD1) % MOD1) * KEY) % MOD1 + sent[i]) % MOD1;
hashB2 = ((((hashB2 - ((sent[i-l] * p2) % MOD2) + MOD2) % MOD2) * KEY) % MOD2 + sent[i]) % MOD2;
if((hashA1 == hashB1) && (hashA2 == hashB2)) {
sol.push(i-l+1);
}
}
k = 0;
fout << sol.size() << '\n';
while(!sol.empty() && (k < 1000)) {
fout << sol.front() << ' ';
sol.pop();
k++;
}
fin.close();
fout.close();
return 0;
}