Cod sursa(job #2541965)

Utilizator IoLeoLeonard Rumeghea IoLeo Data 9 februarie 2020 11:39:51
Problema Potrivirea sirurilor Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.09 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("file.in");
ofstream out("lantminim.out");

char t[256], p[256];

int k, urm[256], contor;

int main(){

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

    //cout << p << " -> " << t << endl;

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

    urm[1] = 0;

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

        urm[i] = k;
    }

    for(int q = 1; 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);
        }
    }

    cout << contor << endl;

    set<int>::iterator it;

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

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