Pagini recente » Cod sursa (job #2389279) | Cod sursa (job #1114128) | Cod sursa (job #2333073) | Cod sursa (job #1664444) | Cod sursa (job #3192449)
#include <bits/stdc++.h>
using namespace std;
#ifndef HOME
ifstream in("strmatch.in");
ofstream out("strmatch.out");
#define cin in
#define cout out
#endif
const int baza = 63, MOD = 1e9 + 7;
int pref[2000001];
string a, b;
int cifra(char c)
{
if('A' <= c && c <= 'Z')
return c - 'A' + 1;
if('a' <= c && c <= 'z')
return c - 'a' + 27;
return c - '0' + 53;
}
int put = 1;
int afis[1001];
int codificare(int i, int j)
{
if(i == 0)
return pref[j];
return (pref[j] - 1LL * pref[i - 1] * put % MOD + MOD) % MOD;
}
int main()
{
#ifdef HOME
freopen("test.in", "r", stdin);
freopen("test.out", "w", stdout);
#endif // HOME
int cod = 0;
cin >> a >> b;
for(int i = 0; i < a.size(); i++)
cod = (1LL * cod * baza + cifra(a[i])) % MOD;
for(int i = 0; i < a.size(); i++)
put = 1LL * put * baza % MOD;
pref[0] = cifra(b[0]);
for(int i = 1; i < b.size(); i++)
pref[i] = (1LL * pref[i - 1] * baza + cifra(b[i])) % MOD;
int cnt = 0;
for(int i = 0; i + a.size() - 1 < b.size(); i++)
if(cod == codificare(i, i + a.size() - 1))
{
cnt++;
if(cnt <= 1000)
afis[cnt] = i;
}
cout << cnt << '\n';
for(int i = 1; i <= min(cnt, 1000); i++)
cout << afis[i] << " ";
return 0;
}