Cod sursa(job #2357661)

Utilizator cyg_TheoPruteanu Theodor cyg_Theo Data 27 februarie 2019 17:18:18
Problema Potrivirea sirurilor Scor 0
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <cstdio>
#include <string.h>

using namespace std;

const int NMAX=2000001;

#define BASE 31
#define MOD1 100007
#define MOD2 100021

char s[NMAX],w[NMAX];
bool match[NMAX];
int cnt=0;

int main()
{
    freopen("strmatch.in","r",stdin);
    freopen("strmatch.out","w",stdout);
    gets(w);
    gets(s);
    int m=strlen(w);
    int n=strlen(s);

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

    int hashW1=0,hashW2=0;
    int hashS1=0,hashS2=0;
    int P1=1,P2=1;
    for(int i=0;i<m;++i){
        hashW1=(hashW1*BASE+w[i])%MOD1;
        hashW2=(hashW2*BASE+w[i])%MOD2;

        if(i!=0){
            P1=(P1*BASE)%MOD1;
            P2=(P2*BASE)%MOD2;
        }
    }

    for(int i=0;i<m;++i){
        hashS1=(hashS1*BASE+s[i])%MOD1;
        hashS2=(hashS2*BASE+s[i])%MOD2;
    }

    if(hashS1==hashW1 && hashS2==hashW2){
        ++cnt;
        match[0]=1;
    }

    for(int i=m;i<n;++i){
            hashS1=((hashS1-(s[i-m]*P1)%MOD1+MOD1)*BASE+s[i])%MOD1;
            hashS2=((hashS2-(s[i-m]*P2)%MOD2+MOD2)*BASE+s[i])%MOD2;

            if(hashS1==hashW1 && hashS2==hashW2){
                ++cnt;
                match[i-m+1]=1;
            }
    }

    printf("%d\n",cnt);

    for(int i=0;i<n;++i)
        if(match[i]==1)
            printf("%d ",i);

    return 0;
}