Cod sursa(job #1054043)

Utilizator AlexNiuclaeNiculae Alexandru Vlad AlexNiuclae Data 13 decembrie 2013 11:47:15
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.54 kb
#include <cstdio>
#include <vector>
#include <cstring>
#define Mod1 666013
#define Mod2 10003
#define p 73

using namespace std;

vector <int> h1[Mod1],h2[Mod2];
vector <int> :: iterator it;

char a[2000001], b[2000001];
int na, nb,i;

int hasha1, hasha2, p1, p2;

char match[2000001];


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

    gets(a);
    gets(b);
    na = strlen(a);
    nb = strlen(b);

    p1 = p2 = 1;
    hasha1 = hasha2 = 0;
    for (int i = 0; i < na; i++)
    {
        hasha1 = (hasha1 * p + a[i]) % Mod1;
        hasha2 = (hasha2 * p + a[i]) % Mod2;

        if (i != 0)
            p1 = (p1 * p) % Mod1,
            p2 = (p2 * p) % Mod2;
    }

    if (na> nb)
    {
        printf("0\n");
        return 0;
    }
  int hash1 = 0, hash2 = 0;
    for (int i = 0; i <na; i++)
        hash1 = (hash1 * p + b[i]) % Mod1,
        hash2 = (hash2 * p + b[i]) % Mod2;

    int Nr = 0;
    if (hash1 == hasha1 && hash2 == hasha2)
       { match[0] = 1; Nr++;}

     for (int i = na; i < nb; i++)
    {
        hash1 = ((hash1 - (b[i - na] * p1) % Mod1 + Mod1) * p + b[i]) % Mod1;
        hash2 = ((hash2 - (b[i - na] * p2) % Mod2 + Mod2) * p + b[i]) % Mod2;

        if (hash1 == hasha1 && hash2 == hasha2)
            match[ i - na + 1 ] = 1, Nr++;
    }
    printf("%d\n", Nr);

    Nr = 0;
    for (int i = 0; i < nb && Nr < 1000; i++)
        if (match[i])
          {
            Nr++;
            printf("%d ", i);
    }



return 0;
}