Cod sursa(job #3169056)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 14 noiembrie 2023 00:28:19
Problema Potrivirea sirurilor Scor 28
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <deque>
#include <algorithm>
#include <vector>
#include <fstream>
#include <iostream>
#include <stack>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#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;

void KMP() {
    string P, T;
    f >> P >> T;
    P = " " + P;
    T = " " + T; 

    int n = P.size();
    vector<int> dpP(n, 0);
    for (int i = 2; i < n; i++) {

        int K = dpP[i - 1];
        while (K > 0 && P[i] != P[K + 1]) K = dpP[K];

        dpP[i] = K + (P[i] == P[K + 1]);
    }

    int m = T.size();
    vector<int> dpT(m, 0);
    int ans = 0;
    vector<int> poz;
    for (int i = 1; i < m; i++) {

        int K = dpT[i - 1];
        while (K > 0 && T[i] != P[K + 1]) K = dpP[K];

        dpT[i] = K + (T[i] == P[K + 1]);

        if (dpT[i] == n - 1) {
            ans++;
            if (ans <= 1000) {
                poz.push_back(i - n + 1);
            }
        }
    }

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

void Z() {
    string P, T;
    f >> P >> T;

    string  S = P + T;
    int n = S.size();
    vector<int> dp(n, 0);

    int ans = 0;
    vector<int> poz;
    int l = 0, r = 0;
    dp[0] = 1;
    for (int i = 1; i < n; i++) {
        int j = min(dp[i - l], r - i + 1);
        while (i + j < n && S[i + j] == S[j]) j++;
        dp[i] = j;
        if (i + j > r) {
            l = i;
            r = i + j;
        }

        if (dp[i] == P.size()) {
            ans++;
            if (ans <= 1000) {
                poz.push_back(i - P.size());
            }
        }

    }

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

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

    Z();

    return 0;
}