Cod sursa(job #2735714)

Utilizator mex7Alexandru Valentin mex7 Data 2 aprilie 2021 18:46:10
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <bits/stdc++.h>
#define ll long long
#define cin fin
#define cout fout
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
string a, b;
int lps[2000004];

int main() {
    cin >> a >> b;

    for (int i = 1; i < a.size(); ) {
        int curr = 0;
        if (a[i] == a[0]) {
            int add = 0;
            while (a[i] == a[add]) {
                add++;
                lps[++i] = add;
            }
        } else
            lps[++i] = 0;
    }
    a = " " + a;
    b = " " + b;

    vector <int> positions;
    int curr = 0, res = 0;
    for (int i = 1; i < b.size(); ) {
        while (b[i] == a[curr + 1] && curr < a.size() && i < b.size()) {
            i++;
            curr++;
        }

        if (curr == a.size() - 1) {
            curr = lps[curr];
            positions.push_back(i - (int)a.size());
        } else if (curr)
            curr = lps[curr];
        else
            i++;
    }

    cout << positions.size() << '\n';
    for (int i : positions)
        cout << i << ' ';
}