Cod sursa(job #2805823)

Utilizator namesurname01Name Surname namesurname01 Data 22 noiembrie 2021 02:11:19
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <stdio.h>
#include <cstring>
using namespace std;
FILE* f, * g;

char x[2000002], y[2000002];
int n, m, ss, v[1004], pi[2000002];

void citire()
{
    fscanf(f, "%s", x);
    fscanf(f, "%s", y);
    m = strlen(x) - 1;
    n = strlen(y) - 1;
}

void kmp()
{
    int k = -1, i;
    pi[0] = -1;
    for (i = 1;i <= m;i++)
    {
        while (k > -1 && x[k + 1] != x[i])
            k = pi[k];
        if (x[k + 1] == x[i])
            k++;
        pi[i] = k;
    }
}

void kmp1()
{
    int i, k = -1;
    for (i = 0;i <= n;i++)
    {
        while (k > -1 && x[k + 1] != y[i])
            k = pi[k];
        if (y[i] == x[k + 1])
            k++;
        if (k == m)
        {
            ss++;
            if (ss <= 1000)
                v[ss] = i - k;
        }
    }
}

void afisare()
{
    int i, mi = 1000;
    /*for(i=1;i<=m;i++)
        fprintf(g,"%d ",pi[i]);
     fprintf(g,"\n");
    */
    fprintf(g, "%d\n", ss);
    if (ss < mi)
        mi = ss;
    for (i = 1;i <= mi;i++)
        fprintf(g, "%d ", v[i]);
}


int main()
{
    f = fopen("strmatch.in", "r");
    g = fopen("strmatch.out", "w");
    citire();
    kmp();
    kmp1();
    afisare();
    fclose(f);
    fclose(g);
    return 0;
}