Cod sursa(job #1082805)

Utilizator AndreeaPanaitAndreea Elena Panait AndreeaPanait Data 14 ianuarie 2014 22:11:53
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.65 kb
#include <string.h>
#include <stdio.h>
#define modul1 100007
#define modul2 100021
#define maxim 2000001
#define x 73

char A[maxim], B[maxim];
int n, m;
int hash_nr1, hash_nr2, x1, x2;
char match[maxim];

int main()
{
    freopen("strmatch.in", "rt", stdin);
    freopen("strmatch.out", "wt", stdout);

    scanf("%s %s", A, B);
    n = strlen(A);
    m = strlen(B);

    x1 = x2 = 1;
    hash_nr1 = hash_nr2 = 0;
    for (int i = 0; i < n; i++)
    {
        hash_nr1 = (hash_nr1 * x + A[i]) % modul1;
        hash_nr2 = (hash_nr2 * x + A[i]) % modul2;

        if (i != 0)
        {
            x1 = (x1 * x) % modul1;
            x2 = (x2 * x) % modul2;
        }
    }

    if (n > m)
    {
        printf("0\n");
        return 0;
    }

    int hash1 = 0, hash2 = 0;
    for (int i = 0; i < n; i++)

    {
        hash1 = (hash1 * x + B[i]) % modul1;
        hash2 = (hash2 * x + B[i]) % modul2;
    }

    int Nr = 0;
    if (hash1 == hash_nr1 && hash2 == hash_nr2)

        {
         match[0] = 1;
         Nr++;
        }

    for (int i = n; i < m; i++)
    {
        hash1 = ((hash1 - (B[i - n] * x1) % modul1 + modul1) * x + B[i]) % modul1;
        hash2 = ((hash2 - (B[i - n] * x2) % modul2 + modul2) * x + B[i]) % modul2;

        if (hash1 == hash_nr1 && hash2 == hash_nr2)

            {
             match[ i - n + 1 ] = 1;
             Nr++;
            }
    }
    printf("%d\n", Nr);

    Nr = 0;
    for (int i = 0; i < m && Nr < 1000; i++)

        if (match[i])

            {
            Nr++;
            printf("%d ", i);
            }

    printf("\n");

    return 0;
}