Cod sursa(job #3142342)

Utilizator AndreiDeltaBalanici Andrei Daniel AndreiDelta Data 20 iulie 2023 17:07:42
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.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);

    string P, T;
    f >> P >> T;

    
    P = " " + P;
    T = " " + T;
    int n = P.size(), m = T.size();

    vector<int> dp(n);
    dp[1] = 0;
    for (int i = 2; i < n; i++) {
        int k = dp[i - 1];
        while (k > 0 && P[k + 1] != P[i]) k = dp[k];
        dp[i] = k + (P[k + 1] == P[i] ? 1 : 0);

    }

    int prev = 0, cnt = 0;
    vector<int> ans;
    for (int i = 1; i < m; i++) {
        int k = prev;
        while (k > 0 && P[k + 1] != T[i]) k = dp[k];
        prev = k + (P[k + 1] == T[i] ? 1 : 0);
        if (prev == n - 1)
        {
            cnt++;
            if(ans.size() < 1000)
                ans.push_back(i - n + 1);
        }
    }

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

    return 0;
}