Cod sursa(job #3242796)

Utilizator BucsMateMate Bucs BucsMate Data 14 septembrie 2024 08:20:43
Problema Potrivirea sirurilor Scor 38
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.97 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

int main()
{
    string a, b, temp = "0";
    input >> a >> b;
    a = temp + a;
    b = temp + b;
    vector<int> T(a.size(), 0);

    int k = 0;
    for(int i = 2; i < a.size(); i++){
        while(k > 0 && a[k+1] != a[i]){
            k = T[k];
        }
        if(a[k+1] == a[i]){
            k++;
        }
        T[i] = k;
    }

    k = 0;
    int nr = 0;
    vector<int> pos;
    for(int i = 2; i < b.size(); i++){
        while(k > 0 && a[k+1] != b[i]){
            k = T[k];
        }
        if(a[k+1] = b[i]){
            k++;
        }
        if(k == a.size()-1){
            pos.push_back(i-a.size()+1);
            nr++;
        }
    }
    output << nr << endl;
    for(int i = 0; i < pos.size(); i++){
        output << pos[i] << " ";
    }

    return 0;
}