Pagini recente » Borderou de evaluare (job #3311373) | Cod sursa (job #2907935) | Borderou de evaluare (job #1287390) | Clasament kl90k90k | Cod sursa (job #3340904)
#include <bits/stdc++.h>
#define int long long
using namespace std;
ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");
const int nmax = 2e6 + 5;
const int mod1 = 1e9 + 7;
const int mod2 = 1e9 + 9;
const int baza = 131;
int val (char c)
{
if (c >= 'a' && c <= 'z')
return c - 'a' + 1;
if (c >= 'A' && c <= 'Z')
return c - 'A' + 27;
return c - '0' + 53;
}
string a, b;
int h1[nmax], h2[nmax], p1[nmax], p2[nmax];
signed main ()
{
fin >> a >> b;
int n = a.size ();
int m = b.size ();
if (n > m)
{
fout << 0;
return 0;
}
int hashA1 = 0, hashA2 = 0;
for (int i = 0; i < n; i++)
{
hashA1 = (hashA1 * baza + val (a[i])) % mod1;
hashA2 = (hashA2 * baza + val (a[i])) % mod2;
}
p1[0] = p2[0] = 1;
for (int i = 1; i <= m; i++)
{
p1[i] = p1[i - 1] * baza % mod1;
p2[i] = p2[i - 1] * baza % mod2;
h1[i] = (h1[i - 1] * baza + val (b[i - 1])) % mod1;
h2[i] = (h2[i - 1] * baza + val (b[i - 1])) % mod2;
}
vector <int> sol;
for (int i = 0; i + n <= m; i++)
{
int cur1 = (h1[i + n] - h1[i] * p1[n] % mod1 + mod1) % mod1;
int cur2 = (h2[i + n] - h2[i] * p2[n] % mod2 + mod2) % mod2;
if (cur1 == hashA1 && cur2 == hashA2)
sol.push_back (i);
}
fout << sol.size () << "\n";
int limit = min ((int)sol.size (), 1000LL);
for (int i = 0; i < limit; i++)
fout << sol[i] << " ";
return 0;
}