Cod sursa(job #3303808)

Utilizator robigiirimias robert robigi Data 18 iulie 2025 00:33:43
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>
#include <vector>
#include <string>
#include <iostream>
#include <cassert>

using namespace std;

void makePrefix(const string &x, vector<int> &longestPrefix)
{
    int n = x.size();
    longestPrefix[0] = 0;
    int j = 0;
    for (int i = 1; i < n; ++i)
    {
        while (j > 0 && x[i] != x[j])
            j = longestPrefix[j - 1];
        if (x[i] == x[j])
        {
            longestPrefix[i] = ++j;
            assert(j < n);
        }
        else
            longestPrefix[i] = 0;
    }
}

void KMP(const string &x, const string &y, const vector<int> &longestPrefix, std::vector<int> &result)
{
    int n = x.size();
    int m = y.size();

    int j = 0; // index for x

    for (int i = 0; i < m; ++i)
    {
        while (j > 0 && y[i] != x[j])
            j = longestPrefix[j - 1];
        if (y[i] == x[j])
        {
            ++j;
            if (j == n)
            {
                result.push_back(i - n + 1);
                j = longestPrefix[j - 1]; // continue searching for more matches
            }
        }
    }
}

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

    string x, y;
    fin >> x >> y;

    int n = x.size();

    std::vector<int> longestPrefix(n);
    makePrefix(x, longestPrefix);

    std::vector<int> result;

    KMP(x, y, longestPrefix, result);

    fout << result.size() << endl;
    int size = result.size();
    for (int i = 0; i < 1000 && i < size; ++i)
    {
        fout << result[i] << " ";
    }
}