Cod sursa(job #3029952)

Utilizator matei.tudoseMatei Tudose matei.tudose Data 17 martie 2023 12:10:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include <fstream>
#include <vector>
using namespace std;

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

vector<int> matches(string s, int target)
{
    // lps[i] este lungimea celui mai lung prefix care este si sufix al sirului pana la index i
    vector<int> lps(s.size());
    lps[0] = 0;
    vector<int> sol;
    for (int i = 1; i < s.size(); i++)
    {
        int cur = lps[i - 1];
        while (cur && s[i] != s[cur])
            cur = lps[cur - 1];
        if (s[i] == s[cur])
            cur++;
        lps[i] = cur;
        if (lps[i] == target)
            sol.push_back(i - 2 * target);
    }
    return sol;
}

int main()
{
    string a, b;
    fin >> a >> b;
    string c = a + "#" + b;
    // pattern + "#" + șirul în care căutăm
    vector<int> sol = matches(c, a.size());
    fout << sol.size() << "\n";
    if (sol.size() > 1000)
        sol.resize(1000);
    for (int x : sol)
        fout << x << " ";
    fout << "\n";
    return 0;
}