Cod sursa(job #2618768)

Utilizator adriangh3Adrian Gheorghiu adriangh3 Data 25 mai 2020 22:39:11
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.89 kb

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 2000010
#define MOD1 100007
#define MOD2 100021
#define d 73

int main()
{
    FILE *in = freopen("strmatch.in", "r", stdin);
    FILE *out = freopen("strmatch.out", "w", stdout);
    char *subsir = (char *)malloc(MAX * sizeof(char));
    char *sir = (char *)malloc(MAX * sizeof(char));
    char c;
    int n = 0;
    int m = 0;
    while ((c = getchar()) != '\n')
    {
        subsir[m++] = c;
    }
    subsir[m] = 0;
    while ((c = getchar()) != '\n' && c != EOF)
    {
        sir[n++] = c;
    }
    sir[n] = 0;
    int h_sir1 = 0;
    int h_subsir1 = 0;
    int h_sir2 = 0;
    int h_subsir2 = 0;
    int h1 = 1;
    int h2 = 1;
    int nr = 0;
    int aparitii[1000];
    for (int i = 0; i < m - 1; i++)
    {
        h1 = (d * h1) % MOD1;
        h2 = (d * h2) % MOD2;
        h_sir1 = (d * h_sir1 + sir[i]) % MOD1;
        h_subsir1 = (d * h_subsir1 + subsir[i]) % MOD1;
        h_sir2 = (d * h_sir2 + sir[i]) % MOD2;
        h_subsir2 = (d * h_subsir2 + subsir[i]) % MOD2;
    }
    h_sir1 = (d * h_sir1 + sir[m - 1]) % MOD1;
    h_subsir1 = (d * h_subsir1 + subsir[m - 1]) % MOD1;
    h_sir2 = (d * h_sir2 + sir[m - 1]) % MOD2;
    h_subsir2 = (d * h_subsir2 + subsir[m - 1]) % MOD2;
    for (int i = 0; i <= n - m; i++)
    {
        if (h_sir1 == h_subsir1 && h_sir2 == h_subsir2)
        {
            if (nr < 1000)
                aparitii[nr] = i;
            nr++;
        }
        if (i != n - m)
        {
            h_sir1 = (d * (h_sir1 - h1 * sir[i]) + sir[i + m]) % MOD1;
            h_sir1 = h_sir1 < 0 ? h_sir1 + MOD1 : h_sir1;
            h_sir2 = (d * (h_sir2 - h2 * sir[i]) + sir[i + m]) % MOD2;
            h_sir2 = h_sir2 < 0 ? h_sir2 + MOD2 : h_sir2;
        }
    }
    printf("%d\n", nr);
    for (int i = 0; i < nr && i < 1000; i++)
    {
        printf("%d ", aparitii[i]);
    }
    fclose(in);
    fclose(out);
    return 0;
}