Cod sursa(job #2010313)

Utilizator Coroian_DavidCoroian David Coroian_David Data 12 august 2017 16:26:58
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 2.31 kb
#include <cstdio>

#include <cstring>
/*
#define M 62

#define MOD1 1000003

#define MOD2 1000033
*/
#define M 73
#define MOD1 100007
#define MOD2 100021

using namespace std;

typedef long long lint;

FILE *f, *g;

int rz[1009];
int rez;

char a[2000009];
char b[2000009];

void readFile()
{
    f = fopen("strmatch.in", "r");

    fscanf(f, "%s", a);
    fscanf(f, "%s", b);

    fclose(f);
}

int nr(char c)
{
    if(c >='0' && c <= '9')
        return c - '0' + 1;

    if(c >= 'a' && c <= 'z')
        return 10 + c - 'a' + 1;

    if(c >= 'A' && c <= 'Z')
        return 10 + 26 + c - 'A' + 1;

    return 0;
}

void solve()
{
    int n = strlen(a);

    int m = strlen(b);

    if(n > m)
    {
        rez = 0;

        return;
    }

    lint p1 = 1;
    lint p2 = 1;

    lint r1 = 0;
    lint r2 = 0;

    int i;
    for(i = 0; i < n; i ++)
    {
        r1 = r1 * M + nr(a[i]);
        r1 %= MOD1;

        r2 = r2 * M + nr(a[i]);
        r2 %= MOD2;

        if(i > 0)
        {
            p1 *= M;
            p1 %= MOD1;

            p2 *= M;
            p2 %= MOD2;
        }
    }

    lint h1 = 0;
    lint h2 = 0;

    for(i = 0; i < n; i ++)
    {
        h1 = h1 * M + nr(b[i]);
        h1 %= MOD1;

        h2 = h2 * M + nr(b[i]);
        h2 %= MOD2;
    }

    if(h1 == r1 && h2 == r2)
        rz[++ rez] = 0;

    for(i = n; i < m; i ++)
    {

      //  printf("%lld %lld\n", h1, h2);

        h1 = h1 - p1 * nr(b[i - n]) % MOD1 + MOD1;
        h1 %= MOD1;

        h1 = h1 * M + nr(b[i]);
        h1 %= MOD1;


        h2 = h2 - p2 * nr(b[i - n]) % MOD2 + MOD2;
        h2 %= MOD2;

        h2 = h2 * M + nr(b[i]);
        h2 %= MOD2;

       // printf("%lld %lld\n", h1, h2);

        /*if(i == 3)
        {
            printf("%lld %lld\n", h1, h2);
            printf("%lld %lld\n", r1, r2);
        }*/

        if(rez < 1000 && h1 == r1 && h2 == r2)
            rz[++ rez] = i - n + 1;
    }
}

void printFile()
{
    g = fopen("strmatch.out", "w");

    fprintf(g, "%d\n", rez);

    int i;
    for(i = 1; i <= rez; i ++)
        fprintf(g, "%d ", rz[i]);

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    solve();

    printFile();

    return 0;
}