Cod sursa(job #3362867)

Utilizator horia.boeriuBoeriu Horia Andrei horia.boeriu Data 12 august 2026 19:56:13
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <iostream>

using namespace std;
const int MAXN = 2000000;
const int MAX = 1000;
char v[MAXN + 1];
int pi[MAXN];//pi[i] = lungimea maxima a sufixului care se termina in i egal cu prefixul(in afara de sufixul de marime i)
int vrez[MAX];
int main()
{
    //kmp
    FILE *fin, *fout;
    int n, i, rez, j;
    char ch;
    fin = fopen("strmatch.in", "r");
    ch = fgetc(fin);
    n = 0;
    while (ch != '\n') {
        v[n] = ch;
        n++;
        ch = fgetc(fin);
    }
    v[n] = -1;//santinela
    j = 0;
    for (i = 1; i < n; i++) {
        while (j > 0 && v[i] != v[j]) {
            j = pi[j - 1];
        }
        if (v[i] == v[j]) {
            j++;
        }
        pi[i] = j;
    }
    ch = fgetc(fin);
    j = rez = i = 0;
    while (ch != '\n' && ch != EOF) {
        i++;
        while (j > 0 && ch != v[j]) {
            j = pi[j - 1];
        }
        if (ch == v[j]) {
            j++;
        }
        if (j == n) {
            if (rez < MAX) {
                vrez[rez] = i - n;
            }
            rez++;
        }
        ch = fgetc(fin);
    }
    fclose(fin);
    fout = fopen("strmatch.out", "w");
    fprintf(fout, "%d\n", rez);
    if (rez > MAX) {
        rez = MAX;
    }
    for (i = 0; i < rez; i++) {
        fprintf(fout, "%d ", vrez[i]);
    }
    fprintf(fout, "\n");
    fclose(fout);
    return 0;
}