Cod sursa(job #2418968)

Utilizator dan.ghitaDan Ghita dan.ghita Data 7 mai 2019 08:41:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1 kb
#include <bits/stdc++.h>
#include <unordered_map>

using namespace std;

ifstream f("strmatch.in");
ofstream g("strmatch.out");

int main()
{
    string s, p;
    f >> p >> s;

    vector<int> pref(p.size(), 0);
    int i = 0, j = 1;
    while (j < p.size())
        if (p[i] == p[j])
            pref[j] = i + 1,
            ++i, ++j;
        else if (i == 0)
            ++j;
        else
            i = pref[i - 1];

    vector<int> matches;
    i = 0, j = 0;
    while (i < s.size())
        if (j == p.size())
        {
            matches.push_back(i - j);
            j = pref[j - 1];
        }
        else if (s[i] == p[j])
            ++i, ++j;
        else if (j == 0)
            ++i;
        else
            j = pref[j - 1];

    if (j == p.size())
        matches.push_back(s.size() - p.size());

    g << matches.size() << '\n';
    if(matches.size() > 1000)
        matches.resize(1000);
    for (auto x : matches)
        g << x << ' ';

    return 0;
}