Pagini recente » Cod sursa (job #323159) | Cod sursa (job #528126) | Cod sursa (job #326692) | Cod sursa (job #695654) | Cod sursa (job #1357416)
#include <fstream>
#include <cstring>
#include <vector>
//#include <algorithm>
#define LMAX 2000005
#define mod 100007
#define base 127
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
char a[LMAX], b[LMAX];
int n, m;
vector <int> sol;
long long a_hash, b_hash;
int main()
{
fin >> a; n = strlen(a);
fin >> b; m = strlen(b);
long long x = 1;
for (int i = 0; i < n; ++i)
{
a_hash = (a_hash * base + a[i]) % mod;
}
for (int i = 1; i < n; ++i) x = (x * base) % mod;
for (int i = 0; i < n; ++i)
b_hash = (b_hash * base + b[i]) % mod;
if (b_hash == a_hash) sol.push_back(0);
for (int i = n; i < m; ++i)
{
b_hash = ((b_hash - ((b[i-n] * x) % mod) + mod) * base + b[i]) % mod;
if (a_hash == b_hash) sol.push_back(i-n+1);
}
int dim = min((int)sol.size(), 1000);
fout << dim << '\n';
for (int i = 0; i < dim; ++i)
fout << sol[i] << ' ';
fout << '\n';
return 0;
}