Cod sursa(job #2713988)

Utilizator Andrei-27Arhire Andrei Andrei-27 Data 1 martie 2021 01:56:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.12 kb
/*
*  Created by Andrei Arhire 01/03/2021
*  Copyright © 2021 Andrei Arhire. All rights reserved.
*  Expected verdict - Accepted
*/
#include <bits/stdc++.h>

#define pb push_back
#define zero(pos) pos&(-pos)
#define eb emplace_back
#define mp make_pair
using namespace std;
const long long NR = 2e6 + 1e2;
const long long oo = 1e16;


string s, t;
vector<int> sol, P(NR, 0);
ifstream in("strmatch.in");
ofstream out("strmatch.out");

signed main() {
    ios::sync_with_stdio(false);
    in.tie(nullptr);
    in >> s >> t;
    int i, L = 0;
    for (i = 1; i < s.size(); ++i) {
        while (L && s[i] != s[L]) {
            L = P[L - 1];
        }
        if (s[i] == s[L]) {
            ++L;
        }
        P[i] = L;
    }
    L = 0;
    for (i = 0; i < t.size(); ++i) {
        while (L && t[i] != s[L]) {
            L = P[L - 1];
        }
        if (t[i] == s[L]) {
            ++L;
        }
        if (L == s.size()) {
            sol.pb(i + 1 - L);
            L = P[L - 1];
        }
    }
    out << sol.size() << '\n';
    for (i = 0; i < min((int) sol.size(), 1000); ++i) {
        out << sol[i] << ' ';
    }
    return 0;
}