Cod sursa(job #1892312)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 24 februarie 2017 21:16:44
Problema Potrivirea sirurilor Scor 14
Compilator cpp Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

#define MAXLEN  2000001

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

#define PRIME 73
#define MOD 100021

typedef unsigned long long LL;

int strlen(char *p)
{
    int i = 0;
    while(*p) i++,p++;

    return i;
}

void citire()
{

    scanf("%s %s ",p,s);
    sl = strlen(s);
    pl = strlen(p);
}

LL compute(char *a,int len)
{
    LL  rez = 0;
    LL prime_power = 1;

    for(int i=0;i<len;i++)
    {
        rez += (a[i]*prime_power);
        rez %= MOD;

        prime_power *= PRIME;
        prime_power %= MOD;
    }

    return rez;
}

LL rolling_hash;
LL prime_power;

LL pow(LL x, LL power)
{
    if(power==1)
        return x % MOD;
    if((power&1)==0)
    {
        LL rez = pow(x,power>>1) % MOD;
        return (rez * rez) % MOD;
    }
    return pow(x,power-1);
}

void compute_prime_power()
{
    prime_power=pow(PRIME,pl);
}

void roll(char add, char rem)
{
   // cout<<"remove "<<rem<<" adding "<<add<<endl;

    rolling_hash -= rem;
    rolling_hash /= PRIME;

    rolling_hash += (add*prime_power);

    rolling_hash %= MOD;
}

bool check(int start)
{
    for(int i=0,j=start; i< pl; i++, j++)
        if(p[i]!=s[j])
            return 0;
    return 1;
}

vector<int> result;

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

    citire();
    compute_prime_power();

    //cout<<prime_power<<endl;

    LL pattern_hash = compute(p,pl);

   // cout<<pattern_hash<<endl;

    rolling_hash = compute(s,pl);


    for(int i=pl; i< sl; i++)
    {
        //cout<<rolling_hash<<endl;

        if(pattern_hash == rolling_hash)
        {
            if(check(i-pl))
            {
                result.push_back(i-pl);
            }
        }

        roll(s[i],s[i-pl]);
    }

    int result_size = result.size();

    printf("%d\n",result_size);
    for(int i=0;i<result_size;i++)
        printf("%d ",result[i]);

    return 0;
}