Cod sursa(job #2870663)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 12 martie 2022 14:52:08
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.78 kb
#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

const string filename = "strmatch";
ifstream fin(filename + ".in");
ofstream fout(filename + ".out");

int n, na, k, pi[4000005], afis;
string a, b, s;
vector <int> v;

int main()
{
    fin >> a >> b;
    s = a + '$' + b;
    n = s.size();
    na = a.size();
    for(int i = 1; i < n; i++)
    {
        k = pi[i - 1];
        while(k > 0 && s[i] != s[k])
            k = pi[k - 1];
        if(s[i] == s[k])
            k++;
        pi[i] = k;
        if(pi[i] == na)
        {
            afis++;
            if(afis <= 1000)
                v.push_back(i - 2 * na);
        }
    }
    fout << afis << '\n';
    for(int elem : v)
        fout << elem << ' ';
    return 0;
}