Pagini recente » Cod sursa (job #132249) | Cod sursa (job #1838374) | Cod sursa (job #337518) | Cod sursa (job #1084639) | Cod sursa (job #1951796)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int NMax = 2e6 + 5;
const int firstMOD = 666013;
const int secondMOD = 10007;
bitset < NMax > good;
int main() {
ios::sync_with_stdio(false);
string a, b;
fin >> a >> b;
int n = (int)a.size();
int m = (int)b.size();
if(n > m) {
fout << 0;
return 0;
}
int firstPatHash, secondPatHash, firstRatio, secondRatio;
firstPatHash = secondPatHash = 0;
firstRatio = secondRatio = 1;
for(int i = 0; i < n; i++) {
firstPatHash = (firstPatHash * 2 + a[i]) % firstMOD;
secondPatHash = (secondPatHash * 3 + a[i]) % secondMOD;
if(i != 0) {
firstRatio = (firstRatio * 2) % firstMOD;
secondRatio = (secondRatio * 3) % secondMOD;
}
}
int firstTextHash, secondTextHash;
firstTextHash = secondTextHash = 0;
for(int i = 0; i < n; i++) {
firstTextHash = (firstTextHash * 2 + b[i]) % firstMOD;
secondTextHash = (secondTextHash * 3 + b[i]) % secondMOD;
}
int ans = 0;
if(firstTextHash == firstPatHash && secondTextHash == secondPatHash) {
good[0] = true;
ans++;
}
for(int i = n; i < m; i++) {
firstTextHash = ((firstTextHash - (b[i - n] * firstRatio) % firstMOD + firstMOD) * 2 + b[i]) % firstMOD;
secondTextHash = ((secondTextHash - (b[i - n] * secondRatio) % secondMOD + secondMOD) * 3 + b[i]) % secondMOD;
if(firstTextHash == firstPatHash && secondTextHash == secondPatHash) {
good[i - n + 1] = true;
ans++;
}
}
fout << ans << "\n";
ans = 0;
for(int i = 0; i < m && ans <= 1000; i++) {
if(good[i] == true) {
ans++;
fout << i << " ";
}
}
return 0;
}