Cod sursa(job #995175)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 7 septembrie 2013 20:46:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp Status done
Runda Arhiva educationala Marime 1.61 kb
#include <stdio.h>
#include <string.h>
#define MAX 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021

int nArr[1000];
char A[MAX], B[MAX];
void rabinKarp(char *str1, char *str2, int *nA, int &nr);
void getHash(char *str, int length, long long &h1, long long &h2, long long &p1, long long &p2);

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

    scanf("%s %s", A, B);
    int nr;

    rabinKarp(A, B, nArr, nr);

    printf("%d\n", nr);

    if(nr >= 1000) nr = 1000;
    for(int i = 0; i < nr; i++)
        printf("%d ", nArr[i]);

    return 0;
}

void rabinKarp(char *str1, char *str2, int *nA, int &nr)
{
    nr = 0;
    int a = strlen(str1), b = strlen(str2);
    long long h1, h2, k1, k2, p1, p2;
    getHash(str1, a, h1, h2, p1, p2);
    getHash(str2, a, k1, k2, p1, p2);
    if (h1 == k1 && h2 == k2)
        nA[0] = 0, nr++;
    for(int i = a; i < b; i++)
    {
        k1 = ((k1 - (str2[i - a] * p1) % MOD1 + MOD1) * P + str2[i]) % MOD1;
        k2 = ((k2 - (str2[i - a] * p2) % MOD2 + MOD2) * P + str2[i]) % MOD2;
        if (h1 == k1 && h2 == k2)
        {
            if(nr < 1000) nA[nr] = i - a + 1;
            nr++;
        }
    }
}

void getHash(char *str, int length, long long &h1, long long &h2, long long &p1, long long &p2)
{
    h1 = h2 = 0;
    p1 = p2 = 1;
    for(int i = 0; i < length; i++)
    {
        h1 = (h1 * P + str[i]) % MOD1;
        h2 = (h2 * P + str[i]) % MOD2;
        if(i != 0)
        {
            p1 = (p1 * P) % MOD1;
            p2 = (p2 * P) % MOD2;
        }
    }
}