Cod sursa(job #1920598)

Utilizator andreigasparoviciAndrei Gasparovici andreigasparovici Data 10 martie 2017 08:37:08
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <cstdio>
#include <vector>
#define NMAX 2000005

#define MOD1 10007
#define MOD2 666013
#define NR1 27
#define NR2 29
using namespace std;

char a[NMAX], b[NMAX];
int n, m, v1, v2, h1, h2, pow1 = 1, pow2 = 1;
vector<int> sol;

void parse()
{
    char *p;
    fseek(stdin,0,SEEK_END);
    int lg = ftell(stdin)+1;
    fseek(stdin,0,SEEK_SET);

    p = new char[lg * sizeof(char)];

    fread(p,sizeof(char),lg,stdin);

    int i;
    for(i=0;p[i]!='\n';a[n++]=p[i++]);
    a[n]=0,i++;
    for(;p[i]!='\n';b[m++]=p[i++]);
    b[m]=0;
}

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

    parse();

    v1 = v2 = 0;

    for(int i=0; i<n; ++i)
    {
        v1 = ((1LL*v1 * NR1) % MOD1 + a[i]) % MOD1;
        v2 = ((1LL*v2 * NR2) % MOD2 + a[i]) % MOD2;

        if(i)
        {
            pow1 =(pow1 * NR1) % MOD1;
            pow2 =(pow2 * NR2) % MOD2;
        }
    }

    for(int i=0;i<n;i++)
    {
        h1 = ((1LL*h1 * NR1) % MOD1 + b[i]) % MOD1;
        h2 = ((1LL*h2 * NR2) % MOD2 + b[i]) % MOD2;
    }

    if(h1==v1 && h2==v2)
    {
        sol.push_back(0);
    }

    for(int i=n;i<m;i++)
    {
        h1 = ((h1 - (b[i-n]*pow1) % MOD1 + MOD1)* NR1 + b[i]) % MOD1;
        h2 = ((h2 - (b[i-n]*pow2) % MOD2 + MOD2)* NR2 + b[i]) % MOD2;

        if(h1==v1 && h2==v2)
        {
            sol.push_back(i-n+1);
        }
    }

    printf("%d\n",sol.size());

    unsigned long long s = sol.size();

    if(s>1000)
        s=1000;

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

    return 0;
}