Cod sursa(job #2541997)

Utilizator IoLeoLeonard Rumeghea IoLeo Data 9 februarie 2020 12:16:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.11 kb
#include <bits/stdc++.h>
#include <set>
#include <queue>
using namespace std;

set<int> ListaVecini[1010];

set<int> Bolnavi;
set<int> Imbolnaviti;

set<int> Lista;

queue<int> ListaNoduri;

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

char t[2000000], p[2000000];

int k = -1, urm[2000000], contor;

int main(){

    in.getline(p, 2000000);
    in.getline(t, 2000000);

    int m = strlen(p) - 1;
    int n = strlen(t) - 1;

    urm[0] = -1;
    k = -1;

    for(int i = 1; i <= m; i++){
        while(k >= 0 && p[i] != p[k + 1])
            k = urm[k];
        if(p[k + 1] == p[i]) k++;

        urm[i] = k;
    }

    k = -1;

    for(int q = 0; q <= n; q++){
        while(k >= 0 && p[k + 1] != t[q])
            k = urm[k];

        if(p[k + 1] == t[q]) k++;

        if(k == m){
            contor++;
            Lista.insert(q - k);
        }
    }

    out << contor << endl;

    set<int>::iterator it;

    for(it = Lista.begin(); it != Lista.end(); it++){

        //cout << *it << " ->" << t + *it << endl;
        out << *it << " ";
    }
}