Cod sursa(job #995177)

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

int nA[1000];
char str1[MAX], str2[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;
    long long 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] = 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++;
        }
    }

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

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

    return 0;
}