Cod sursa(job #3142569)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 22 iulie 2023 15:42:09
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#include <math.h>
#define pb push_back
using namespace std;
ifstream f("strmatch.in");
ofstream g("strmatch.out");
typedef long long ll;
typedef pair<int, int> pi;
int t, T;

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

    int cnt = 0;
    vector<int> ans;

    string P, T;
    f >> P >> T;
    
    int n = P.size();
    int m = T.size();
    vector<int> zP(n, 0), zT(m, 0);

    int l = 0, r = 0;
    for (int i = 1; i < n; i++) {
        if (i < r) {
            zP[i] = min(r - i, zP[i - l]);
        }

        while (i + zP[i] < n && P[zP[i]] == P[i + zP[i]]) {
            zP[i]++;
        }

        if (i + zP[i] > r) {
            l = i;
            r = i + zP[i];
        }
    }

    l = 0, r = 0;
    int prev = 0;
    for (int i = 0; i < m; i++) {
        prev = 0;
        if (i < r) {
            prev = min(r - i, zP[i - l]);
        }

        while (i + prev < m && prev < n && P[prev] == T[i + prev]) prev++;

        if (i + prev > r) {
            l = i;
            r = i + prev;
        }

        if (prev == n) {
            cnt++;
            if (ans.size() < 1000) {
                ans.push_back(i);
            }
        }
    }

    g << cnt << '\n';
    for (int x : ans) g << x << ' ';

    return 0;
}