Pagini recente » Cod sursa (job #2658663) | Cod sursa (job #2615873) | Cod sursa (job #2663236) | Cod sursa (job #927010) | Cod sursa (job #2654333)
#include <iostream>
#include <string>
#include <algorithm>
#include <climits>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
const long long b1 = 97;
const long long MOD = 666013;
const long long b2 = 113;
const long long MOD1 = 177013;
string a, b;
vector<int>sol;
int main()
{
getline(fin, a);
getline(fin, b);
long long hashA = 0;
long long hashB = 0;
long long hashA1 = 0;
long long hashB1 = 0;
long long na = a.size();
long long nb = b.size();
long long put = 1;
long long put1 = 1;
for (int i = 0; i < na; i++) {
hashA = ((hashA * b1) % MOD + a[i]) % MOD;
put = (put * b1) % MOD;
hashA1 = ((hashA1 * b2) % MOD1 + a[i]) % MOD1;
put1 = (put1 * b2) % MOD1;
}
for (int i = 0; i < nb; i++) {
hashB = ((hashB * b1) % MOD + b[i]) % MOD;
hashB1 = ((hashB1 * b2) % MOD1 + b[i]) % MOD1;
}
long long cnt = 0;
if (hashA == hashB && na == nb && hashB1 == hashA1) {
cnt++;
sol.push_back(1);
}
hashB = 0;
hashB1 = 0;
for (int i = 0; i < na; i++) {
hashB = ((hashB * b1) % MOD + b[i]) % MOD;
hashB1 = ((hashB1 * b2) % MOD1 + b[i]) % MOD1;
}
for (int i = na; i < nb; i++)
{
hashB = ((hashB * b1) % MOD + b[i]) % MOD;
long long value = (put * b[i - na]);
hashB = ((hashB - value) % MOD + MOD) % MOD;
hashB1 = ((hashB1 * b2) % MOD1 + b[i]) % MOD1;
long long value1 = (put1 * b[i - na]);
hashB1 = ((hashB1 - value1) % MOD1 + MOD1) % MOD1;
if (hashA == hashB && hashA1 == hashB1)
{
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;
}