Cod sursa(job #2847656)

Utilizator vladvlad00Vlad Teodorescu vladvlad00 Data 11 februarie 2022 10:56:17
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <cstring>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <cmath>
#include <functional>
#include <stack>
#include <iomanip>
#include <list>
#include <chrono>
#include <random>
#include <numeric>

using namespace std;

ifstream cin("strmatch.in");
ofstream cout("strmatch.out");

vector<int> prefix_function(const string& s)
{
    int n = s.length();
    vector<int> pi(n);

    for (int i = 1; i < n; i++)
    {
        int j = pi[i - 1];
        while (j && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string s, t;
    cin >> t >> s;
    auto pi = prefix_function(t);
    int j = 0;
    vector<int> sol;
    for (int i = 0; i < s.length(); i++)
    {
        while (j && s[i] != t[j])
            j = pi[j - 1];
        if (s[i] == t[j])
            j++;
        if (j == t.length())
        {
            sol.push_back(i - j + 1);
            j = pi[j - 1];
        }
    }
    cout << sol.size() << '\n';
    for (int i=0;i<min(1000,(int)sol.size());i++)
    {
        cout << sol[i] << ' ';
    }
    cout << '\n';
    return 0;
}