Cod sursa(job #3170201)

Utilizator MihaelaCismaruMihaela Cismaru MihaelaCismaru Data 16 noiembrie 2023 22:43:52
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.85 kb
#include<fstream>
using namespace std;
ifstream in ("strmatch.in");
ofstream out ("strmatch.out");
int i,j,pi[2000005], potriviri[10005];
string s1,s2;
int main (void) {
    in >> s1;
    in >> s2;

    pi[0] = -1;
    j = -1;
    for (int i = 0; i < s1.size(); i ++) {
        while (j >= 0 && s1[i] != s1[j]) {
            j = pi[j];
        }
        pi[i+1] = ++j;
    }

    int occ = 0;
    j = 0;
    for (int i = 0; i < s2.size(); i ++) {
        while (j >= 0 && s2[i] != s1[j]) {
            j = pi[j];
        }
        j ++;
        if (j == s1.size()) {
            occ ++;
            if (occ <= 1000)
                potriviri[occ] = i-s1.size()+1;
            j = pi[j];
        }
    }
    out << occ <<"\n";
    for (int i = 1; i <= min(occ,1000); i ++) {
        out << potriviri[i] <<" ";
    }

    return 0;
}