Cod sursa(job #2964598)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 13 ianuarie 2023 13:24:01
Problema Potrivirea sirurilor Scor 18
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#define MAX_N 2000005
using namespace std;
char a[MAX_N], b[MAX_N];
FILE *fin=fopen("strmatch.in", "r");
FILE *fout=fopen("strmatch.out", "w");
int lps[MAX_N];
vector <int> contor;
int main()
{
    fscanf(fin, "%s", a);
    fscanf(fin, "%s", b);
    int len=0, lenA=strlen(a);
    for (int i=1; a[i]!='\0'; i++) {
        if (a[len]==a[i]) {
            len++;
            lps[i]=len;
        }
        else {
            if (len>0) {
                len=lps[len-1];
                i--;
            }
        }
    }
    int indexA=0, indexB=0, start_poz=-1;
    for (indexB=0; b[indexB]!='\0'; indexB++) {
        if (a[indexA]=='\0') {
            contor.push_back(start_poz);
            indexA=lps[indexA-1];
            start_poz=indexB-indexA+1;
            indexB--;
        }
        if (a[indexA]==b[indexB]) {
            if (start_poz==-1) start_poz=indexB;
            indexA++;
        }
        else {
            if (indexA!=0) {
                indexA=lps[indexA-1];
                indexB--;
            }
            start_poz=indexB-indexA+1;
        }
    }
    if (a[indexA]=='\0') {
        contor.push_back(start_poz);
        indexA=lps[indexA-1];
        start_poz=indexB-indexA+1;
        indexB--;
    }
    fprintf(fout, "%d\n", contor.size());
    int last_poz=contor.size();
    if (contor.size()>1000) last_poz=1000;
    for (int i=0; i<last_poz; i++) {
        fprintf(fout, "%d ", contor[i]);
    }
    return 0;
}