Cod sursa(job #1963704)

Utilizator fluture.godlikeGafton Mihnea Alexandru fluture.godlike Data 12 aprilie 2017 18:27:57
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.88 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define in "strmatch.in"
#define out "strmatch.out"
#define NMAX (2000000 + 7)
#define MOD (1000000000 + 7)
#define MOD2 666013
#define pb push_back
#define phi 52

using namespace std;
int szeA, szeB, pw[NMAX], hashValue, Hash, sze, hashValue2, Hash2, pw2[NMAX];
char A[NMAX], B[NMAX];
vector <int> sol;

int val(char ch) // OK
{
    if(ch == 0) return 0;
    if(ch <= 'z' && ch >= 'a') return (ch-'a');
    return (26 + ch - 'A');
}

int main()
{
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
    scanf("%s\n%s\n", A+1, B+1);
    szeA = strlen(A+1);
    szeB = strlen(B+1);
    pw[0] = 1;
    for(int i = 1; i<= szeA; ++i) pw[i] = (1LL * pw[i-1] * phi)%MOD;
    pw2[0] = 1;
    for(int i = 1; i<= szeA; ++i) pw2[i] = (1LL * pw2[i-1] * phi)%MOD2;
    for(int i = 1; i<= szeA; ++i) hashValue = (1LL*hashValue*phi + val(A[i]))%MOD;
    for(int i = 1; i<= szeA; ++i) hashValue2 = (1LL*hashValue2*phi + val(A[i]))%MOD2;
    for(int i = 1; i<= szeB; ++i)
    {
        if(i >= szeA)
        {
            Hash = (Hash - (1LL * val(B[i-szeA]) * pw[szeA-1]) % MOD + MOD)%MOD;
            Hash2 = (Hash2 - (1LL * val(B[i-szeA]) * pw2[szeA-1]) % MOD2 + MOD2)%MOD2;
        }
        Hash = (1LL * Hash * phi + val(B[i]))%MOD;
        Hash2 = (1LL * Hash2 * phi + val(B[i]))%MOD2;
        if(i >= szeA)
        {
            if(Hash == hashValue && Hash2 == hashValue2)
            {
                bool f = 1;
                for(int j = 1; j<= szeA; ++j)
                {
                    if(A[j] != B[i-szeA + j]) {f = 0; break;}
                }
                if(f == 1) sol.pb(i-szeA);
            }
        }
    }
    sze = sol.size();
    printf("%d\n", sze);
    for(int i = 0; i< min(1000, sze); ++i) printf("%d ", sol[i]);
    printf("\n");
    return 0;
}