Cod sursa(job #3163482)

Utilizator adelina_15InfoAdelina Radoi adelina_15Info Data 31 octombrie 2023 15:11:59
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.76 kb
#include <iostream>
#include <fstream>
#include <string>
#include <vector>

using namespace std;

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

string a, b, c;

vector<int> pi;
vector<int> v;

int main()
{
    fin >> a >> b;
    c = a + '#' + b;

    int k = 0;
    pi.resize(c.size());
    pi[0] = 0;

    int n = a.size();
    int rasp = 0;
    for(int i = 1; i < c.size(); i++)
    {
        while(k != 0 && c[k] != c[i])
            k = pi[k-1];

        if(c[k] == c[i])
            k++;
        if(k == n)
        {
            rasp++;
            v.push_back(i-n-k);
        }
        pi[i] = k;
    }
    fout << rasp << "\n";
    for(int i = 0; i < rasp; i++)
        fout << v[i] << " ";
    return 0;
}