Pagini recente » Cod sursa (job #2883330) | Cod sursa (job #2822580) | Cod sursa (job #178197) | Cod sursa (job #353658) | Cod sursa (job #1357787)
#include <fstream>
#include <iostream>
#include <cstring>
#include <vector>
//#include <algorithm>
#define LMAX 2000005
#define mod1 100007
#define mod2 100021
#define base1 127
#define base2 126
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
//char a[LMAX], b[LMAX];
string a, b;
int n, m;
vector <int> sol;
long long a_hash1, b_hash1;
long long a_hash2, b_hash2;
int main()
{
fin >> a; n = (a.size());
fin >> b; m = (b.size());
long long x1 = 1, x2 = 1;
sol.reserve(1005);
for (int i = 0; i < n; ++i)
{
a_hash1 = (a_hash1 * base1 + a[i]) % mod1;
a_hash2 = (a_hash2 * base2 + a[i]) % mod2;
}
for (int i = 1; i < n; ++i)
{
x1 = (x1 * base1) % mod1;
x2 = (x2 * base2) % mod2;
}
for (int i = 0; i < n; ++i)
{
b_hash1 = (b_hash1 * base1 + b[i]) % mod1;
b_hash2 = (b_hash2 * base2 + b[i]) % mod2;
}
if (b_hash1 == a_hash1 && b_hash2 == a_hash2) sol.push_back(0);
for (int i = n; i < m; ++i)
{
b_hash1 = ((b_hash1 - ((b[i-n] * x1) % mod1) + mod1) * base1 + b[i]) % mod1;
b_hash2 = ((b_hash2 - ((b[i-n] * x2) % mod2) + mod2) * base2 + b[i]) % mod2;
if (a_hash1 == b_hash1 && a_hash2 == b_hash2) sol.push_back(i-n+1);
}
int dim = min((int)sol.size(), 1000);
fout << sol.size() << '\n';
for (int i = 0; i < dim; ++i)
fout << sol[i] << ' ';
fout << '\n';
return 0;
}