Pagini recente » Cod sursa (job #1925744) | Cod sursa (job #2679895) | Cod sursa (job #722963) | Cod sursa (job #2047350) | Cod sursa (job #2654331)
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const int b1 = 97;
const int MOD = 666013;
string a, b;
vector<int>sol;
int main()
{
getline(fin, a);
getline(fin, b);
int hashA = 0;
int hashB = 0;
int put1 = 1;
int na = a.size();
int nb = b.size();
int put = 1;
for (int i = 0; i < na; i++) {
hashA = ((hashA * b1) % MOD + a[i]) % MOD;
put = (put * b1) % MOD;
}
for (int i = 0; i < nb; i++)
hashB = ((hashB * b1) % MOD + b[i]) % MOD;
int cnt = 0;
if (hashA == hashB && na == nb) {
cnt++;
sol.push_back(1);
}
hashB = 0;
for(int i = 0 ; i < na ; i++)
hashB = ((hashB * b1) % MOD + b[i]) % MOD;
for (int i = na; i < nb; i++)
{
hashB = ((hashB * b1) % MOD + b[i]) % MOD;
int value = (put * b[i - na]);
hashB = ((hashB - value) % MOD + MOD) % MOD;
if (hashA == hashB)
{
cnt++;
if (cnt <= 1000)
sol.push_back(i - na + 1);
else
break;
}
}
fout << cnt << "\n";
for (int i = 0; i < sol.size(); i++)
fout << sol[i] << " ";
fout << "\n";
return 0;
}