Pagini recente » Cod sursa (job #894306) | Cod sursa (job #872221) | Cod sursa (job #131990) | Cod sursa (job #1295973) | Cod sursa (job #1824001)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define in "strmatch.in"
#define out "strmatch.out"
#define MOD1 666013
#define DIM (2000000 + 7)
#define sigma 62
#define pb push_back
using namespace std;
int sze1, sze2, modval, checkmod, pw[DIM];
char s1[DIM], s2[DIM];
vector <int> sol;
inline void build()
{
pw[0] = 1;
for(int i = 1; i< DIM; ++i) pw[i] = (pw[i-1] * sigma) % MOD1;
}
int value(char ch)
{
if(ch <= '9' && ch >= '0') return ch - '0';
if(ch <= 'Z' && ch >= 'A') return 10 + ch - 'A';
if(ch <= 'z' && ch >= 'a') return 36 + ch - 'a';
return 0;
}
int main()
{
freopen(in, "r", stdin);
freopen(out, "w", stdout);
build();
scanf("%s %s", s1+1, s2+1);
sze1 = strlen(s1+1);
sze2 = strlen(s2+1);
for(int i = 1; i<= sze1; ++i) modval = (modval + pw[sze1 - i] * value(s1[i])) % MOD1;
for(int i = 1; i< sze1; ++i) checkmod = (checkmod + pw[sze1 - i] * value(s2[i])) % MOD1;
for(int i = sze1; i<= sze2; ++i)
{
checkmod = checkmod + value(s2[i]);
if(checkmod >= MOD1) checkmod -= MOD1;
if(checkmod == modval) sol.pb(i);
checkmod = checkmod - (pw[sze1-1] * value(s2[i-sze1+1])) % MOD1 + MOD1;
checkmod = (checkmod * pw[1])%MOD1;
}
int sz = sol.size();
printf("%d\n", sz);
for(int i = 0; i< min(sz, 1000); ++i) printf("%d ", sol[i]- sze1);
printf("\n");
return 0;
}