Cod sursa(job #3144421)

Utilizator al.mocanuAlexandru Mocanu al.mocanu Data 8 august 2023 00:39:26
Problema Potrivirea sirurilor Scor 20
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.04 kb
#include <fstream>
#include <vector>
using namespace std;


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

    string a, b;

    f >> a >> b;
    vector<int> p(a.length());

    p[0] = 1;
    int pos = 0;
    for (int i = 1; i < a.length(); ++i) {
        while (pos > 0 && a[pos] != a[i])
            pos = p[pos];

        if (a[pos] == a[i]) {
            p[i] = pos + 1;
            pos += 1;
        }
        else {
            p[i] = 0;
            pos = 0;
        }
    }

    int i = 0, j = 0;
    vector<int> match_pos;
    while (j < b.length()) {
        if (match_pos.size() == 1000)
            break;
        if (a[i] == b[j]) {
            if (i == a.length() - 1) {
                match_pos.push_back(j - a.length() + 1);
                i = p[i];
            }
            else
                ++i;
            ++j;
        }
        else if (i == 0)
            ++j;
        else
            i = p[i];
    }

    g << match_pos.size() << "\n";
    for (auto pos : match_pos)
        g << pos << " ";

    return 0;
}