Cod sursa(job #2618754)

Utilizator adriangh3Adrian Gheorghiu adriangh3 Data 25 mai 2020 22:17:09
Problema Potrivirea sirurilor Scor 26
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.62 kb
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX 200001
#define MOD 1000021
#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_sir = 0;
    int h_subsir = 0;
    int h = 1;
    int nr = 0;
    int aparitii[1000];
    for (int i = 0; i < m - 1; i++)
    {
        h = (d * h) % MOD;
        h_sir = (d * h_sir + sir[i]) % MOD;
        h_subsir = (d * h_subsir + subsir[i]) % MOD;
    }
    h_sir = (d * h_sir + sir[m - 1]) % MOD;
    h_subsir = (d * h_subsir + subsir[m - 1]) % MOD;
    for (int i = 0; i <= n - m; i++)
    {
        if (h_sir == h_subsir)
        {
            int j;
            for (j = 0; j < m; j++)
            {
                if (subsir[j] != sir[i + j])
                    break;
            }
            if (j == m)
            {
                if (nr < 1000)
                    aparitii[nr] = i;
                nr++;
            }
        }
        if (i != n - m)
        {
            h_sir = (d * (h_sir - h * sir[i]) + sir[i + m]) % MOD;
            h_sir = h_sir < 0 ? h_sir + MOD : h_sir;
        }
    }
    printf("%d\n", nr);
    for (int i = 0; i < nr && i < 1000; i++)
    {
        printf("%d ", aparitii[i]);
    }
    fclose(in);
    fclose(out);
    return 0;
}