Pagini recente » Cod sursa (job #1249752) | Cod sursa (job #1341860) | Cod sursa (job #269073) | Cod sursa (job #3129595) | Cod sursa (job #2963832)
using namespace std;
#ifdef EZ
#include "./ez/ez.h"
const string FILE_NAME = "test";
#else
#include <bits/stdc++.h>
const string FILE_NAME = "strmatch";
#endif
#define mp make_pair
#define mt make_tuple
#define ll long long
#define pb push_back
#define fi first
#define se second
#define cin fin
#define cout fout
ifstream fin (FILE_NAME + ".in");
ofstream fout (FILE_NAME + ".out");
const int nMAX = 2e6;
const int BAZA = 31;
const int MOD = 1e9 + 7;
int n, m;
char a[nMAX + 2];
char b[nMAX + 2];
int pBaza[nMAX + 1]; // pBaza[i] = BAZA ^ i
int ahash; // ahash = hash-ul stringului a
int bhash[nMAX + 1]; // bhash[i] = hash-ul stringului b[1..i]
int main()
{
cin >> a+1 >> b+1;
n = strlen(a+1);
m = strlen(b+1);
for (int i = 1; i <= n; ++i)
ahash = (1LL * ahash * BAZA + a[i]-'0') % MOD;
for (int i = 1; i <= m; ++i)
bhash[i] = (1LL * bhash[i-1] * BAZA + b[i]-'0') % MOD;
pBaza[0] = 1;
for (int i = 1; i <= nMAX; ++i)
pBaza[i] = 1LL * pBaza[i-1] * BAZA % MOD;
vector<int> ap;
for (int i = 1; i <= m-n+1; ++i)
{
int st = i;
int dr = i+n-1;
int hsh = bhash[dr] - 1LL * bhash[st-1] * pBaza[n] % MOD;
hsh = (hsh+MOD) % MOD;
if (hsh == ahash)
ap.pb(st-1);
}
cout << ap.size() << '\n';
for (int x : ap)
cout << x << ' ';
}