Pagini recente » Cod sursa (job #1401561) | Cod sursa (job #1660921) | Cod sursa (job #258831) | Cod sursa (job #2370860) | Cod sursa (job #1824002)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#define in "strmatch.in"
#define out "strmatch.out"
#define MOD1 666013
#define MOD2 100007
#define DIM (2000000 + 7)
#define sigma 62
#define pb push_back
using namespace std;
int sze1, sze2, modval1, checkmod1, pw1[DIM], pw2[DIM], modval2, checkmod2;
char s1[DIM], s2[DIM];
vector <int> sol;
inline void build()
{
pw1[0] = 1;
for(int i = 1; i< DIM; ++i) pw1[i] = (pw1[i-1] * sigma) % MOD1;
pw2[0] = 1;
for(int i = 1; i< DIM; ++i) pw2[i] = (pw2[i-1] * sigma) % MOD2;
}
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)
{
modval1 = (modval1 + pw1[sze1 - i] * value(s1[i])) % MOD1;
modval2 = (modval2 + pw2[sze1 - i] * value(s1[i])) % MOD2;
}
for(int i = 1; i< sze1; ++i)
{
checkmod1 = (checkmod1 + pw1[sze1 - i] * value(s2[i])) % MOD1;
checkmod2 = (checkmod2 + pw2[sze1 - i] * value(s2[i])) % MOD2;
}
for(int i = sze1; i<= sze2; ++i)
{
checkmod1 = checkmod1 + value(s2[i]);
if(checkmod1 >= MOD1) checkmod1 -= MOD1;
checkmod2 = checkmod2 + value(s2[i]);
if(checkmod2 >= MOD2) checkmod2 -= MOD2;
if(checkmod1 == modval1 && checkmod2 == modval2) sol.pb(i);
checkmod1 = checkmod1 - (pw1[sze1-1] * value(s2[i-sze1+1])) % MOD1 + MOD1;
checkmod1 = (checkmod1 * pw1[1])%MOD1;
checkmod2 = checkmod2 - (pw2[sze1-1] * value(s2[i-sze1+1])) % MOD2 + MOD2;
checkmod2 = (checkmod2 * pw2[1])%MOD2;
}
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;
}