Cod sursa(job #2791181)

Utilizator Aldea_IuliaAldea Iulia-Maria Aldea_Iulia Data 30 octombrie 2021 10:43:14
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <iostream>
#include <cstring>
#include <fstream>
using namespace std;

ifstream fin ("strmatch.in");
ofstream fout ("strmatch.out");

#define  LMAX 2000005

char s[LMAX]; /// stringul in care cautam
char p[LMAX]; /// stringul cautat
int P[LMAX]; /// Sirul cu prefixe
int fi[1005];
int n, m, o;

void formare_Prefixe() {
    int i=0, j=-1;

    P[0] = -1;

    while (i<m) {
        while(j>=0 && p[i]!=p[j])
            j=P[j];

        i++; j++;
        P[i]=j;
    }
}

void kmp() {
    int i=0, j=0;

    while(i<n) {
        while(j>=0 && s[i]!=p[j])
            j=P[j];

        i++; j++;

        if(j==m) {
            j=P[j];
            o++;

            if(o<=1000)
                fi[o] = i-m;
        }
    }
}

void afish() {
    fout << o << "\n";

    if(o>1000)
        o=1000;
    for(int i=1;i<=o;i++)
        fout << fi[i] << " ";
}

int main() {
    fin >> p >> s;

    m=strlen(p);
    n=strlen(s);

    formare_Prefixe();
    kmp();
    afish();




    return 0;
}