Cod sursa(job #1247017)

Utilizator FayedStratulat Alexandru Fayed Data 21 octombrie 2014 22:43:07
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.18 kb
#include <cstdio>
#include <cstring>
#include <cmath>
#define q 666019

int n,m,nr,k;
char Text[2000001];
char pattern[2000001];
int Sol[2000000];

void Rabin_Karp(char *s1, char* s2){

    int P = 0;
    int T = 0;
    m = strlen(s1);
    n = strlen(s2);
    int hashf = 1;
    int ALPHABET = 123;

    for(register int i=1;i<m;++i)
        hashf = hashf*ALPHABET;
        hashf = hashf%q;

    for(register int i=0;i<m;++i){

        P = (P*ALPHABET + s1[i]) % q;
        T = (T*ALPHABET + s2[i]) % q;
    }

    for(register int i=0; i<=n-m;++i){

        if(P == T){

            int j;
            for(j=0;j<m;++j)
                if(s1[j] != s2[i+j])
                    break;
            if(j == m){

                Sol[++k] = i;
                nr++;
        }
    }

        T = (T + ALPHABET*q - s2[i]*hashf)%q;
        T = (T*ALPHABET + s2[i+m])%q;
    }
}

int main(){

    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    scanf("%s",pattern);
    scanf("%s",Text);

    Rabin_Karp(pattern,Text);
    printf("%d\n",nr);
    for(register int i=1;i<=k;++i)
        printf("%d ",Sol[i]);

return 0;
}