Cod sursa(job #3169037)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 13 noiembrie 2023 23:25:27
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 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 << ' ';
    
}

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

    KMP();

    return 0;
}