Cod sursa(job #1890975)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 23 februarie 2017 17:24:31
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

#define MAX_LENGTH 2000005

#define PRIM 101

#define MOD 1000007

char s[MAX_LENGTH], p[MAX_LENGTH];
int sl, pl;

int ap[MAX_LENGTH];

int max_prime_power;

int power(int x,int p)
{
    if(p==1) return x;

    if((p&1) == 0)
    {
        int pt = (power(x,p>>1))%MOD;
        return (pt*pt)%MOD;
    }
    return (x*power(x,p-1))%MOD;
}

void citire()
{
    scanf("%s %s",p,s);
    pl = strlen(p);
    sl = strlen(s);

    max_prime_power = power(PRIM,pl-1);
}

int compute_hash(char a[], int i, int j)
{
    int prim_pow = 1, sum = 0;
    for(int t = i; t<=j; t++)
    {
        sum += ((a[t]-'A'+1)*prim_pow);
        sum%=MOD;
        prim_pow *= PRIM;
    }
    return sum;
}

int recompute_hash(int actual_hash,char a[],int i,int len)
{

    int new_hash = actual_hash - (a[i-len]-'A'+1);
    new_hash /= PRIM;

    new_hash += (a[i]-'A'+1)*max_prime_power;
    new_hash%=MOD;

    return new_hash;
}

bool is_match(int i)
{
    for(int t=0;t<pl-1;t++)
        if(p[t]!=s[t+i])
            return false;
    return true;
}

int ph, sh;

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

    citire();

    ph = compute_hash(p,0,pl-1);
    sh = compute_hash(s,0,pl-1);

    for(int i = pl ; i<= sl-pl+1 ; i++)
    {
        sh = recompute_hash(sh,s,i,pl);

        if(sh==ph && is_match(i))
        {
            ap[++ap[0]]=i-pl+1;
        }
    }
    printf("%d\n",ap[0]);

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

    return 0;
}