Cod sursa(job #995179)

Utilizator cosmo0093Raduta Cosmin cosmo0093 Data 7 septembrie 2013 21:09:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.3 kb
#include <stdio.h>
#include <string.h>
#define MAX 2000001
#define P 73
#define MOD1 100007
#define MOD2 100021

char str1[MAX], str2[MAX], nA[MAX];

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

    scanf("%s %s", str1, str2);

    int a = strlen(str1), b = strlen(str2), nr = 0;
    int h1 = 0, h2 = 0, k1 = 0, k2 = 0, p1 = 1, p2 = 1;

    for(int i = 0; i < a; i++)
    {
        h1 = (h1 * P + str1[i]) % MOD1;
        h2 = (h2 * P + str1[i]) % MOD2;
        if(i != 0)
        {
            p1 = (p1 * P) % MOD1;
            p2 = (p2 * P) % MOD2;
        }
    }

    for(int i = 0; i < a; i++)
    {
        k1 = (k1 * P + str2[i]) % MOD1;
        k2 = (k2 * P + str2[i]) % MOD2;
    }

    if (h1 == k1 && h2 == k2)
        nA[0] = 1, 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)
            nA[i - a + 1] = 1, nr++;
    }

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

    nr = 0;
    for(int i = 0; i < MAX && nr < 1000; i++)
        if(nA[i])
        {
            printf("%d ", i);
            nr++;
        }
    printf("\n");
    return 0;
}