Cod sursa(job #1824001)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 7 decembrie 2016 09:55:23
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#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;
}