Cod sursa(job #1983322)

Utilizator raluca1234Tudor Raluca raluca1234 Data 21 mai 2017 17:28:49
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.62 kb
#include <cstdio>
#include <cstring>

#define lgMax 2000000
#define posMax 1000

#define MOD1 666013
#define MOD2 1000003
#define BASE 63

using namespace std;

char A[lgMax+1], B[lgMax+1];
int pos[posMax+1];

int conv(char ch){
    if (ch>='0' && ch<='9')
        return ch-'0'+1;
    if (ch>='a' && ch<='z')
        return ch-'a'+11;
    if (ch>='A' && ch<='Z')
        return ch-'A'+37;
}

int main(){
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    scanf("%s\n%s", &A, &B);

    int NA=strlen(A), NB=strlen(B);

    if (NA>NB){
        printf("0\n");
        return 0;
    }

    int hashA1, hashA2, hashB1, hashB2;
    hashA1=hashA2=hashB1=hashB2=0;

    int P1, P2;
    P1=P2=1;

    for (int i=0; i<NA; i++){
        hashA1=(hashA1*BASE+conv(A[i]))%MOD1;
        hashA2=(hashA2*BASE+conv(A[i]))%MOD2;

        hashB1=(hashB1*BASE+conv(B[i]))%MOD1;
        hashB2=(hashB2*BASE+conv(B[i]))%MOD2;

        if (i>0)
            P1=(P1*BASE)%MOD1,
            P2=(P2*BASE)%MOD2;
    }

    int nrPos=0;
    if (hashA1==hashB1 && hashA2==hashB2)
        pos[++nrPos]=0;

    for (int i=NA; i<NB; i++){
        hashB1=((hashB1 - (conv(B[i-NA]) * P1)%MOD1 + MOD1)*BASE + conv(B[i]))%MOD1;
        hashB2=((hashB2 - (conv(B[i-NA]) * P2)%MOD2 + MOD2)*BASE + conv(B[i]))%MOD2;

        if (hashA1==hashB1 && hashA2==hashB2){
            nrPos++;
            if (nrPos<=posMax)
                pos[nrPos]=i-NA+1;
        }
    }

    printf("%d\n", nrPos);
    for (int i=1; i<=nrPos && i<=posMax; i++)
        printf("%d ", pos[i]);

    return 0;
}