Cod sursa(job #3283451)

Utilizator paulihno15Ciumandru Paul paulihno15 Data 9 martie 2025 16:45:30
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.02 kb
#include <bits/stdc++.h>
#define NMAX 2000000
#define ll long long
#define ull unsigned long long

using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

string s, t;
int pi[NMAX + 3];

void kmp(string &s, int *pi) {
    int k = 0;
    for (int i = 1; i < s.size(); i++) {
        while (k > 0 && s[i] != s[k]) {
            k = pi[k - 1];
        }
        if (s[i] == s[k]) {
            k++;
        }
        pi[i] = k;
    }
}

int main() {
    fin >> s >> t;
    kmp(s, pi);
    int k = 0;
    vector<int> ans;
    for (int i = 0; i < t.size(); i++) {
        while (k > 0 && t[i] != s[k]) {
            k = pi[k - 1];
        }
        if (t[i] == s[k]) {
            k++;
        }
        if (k == s.size()) {
            ans.push_back(i - s.size() + 1);
            k = pi[k - 1];
        }
    }

    fout << ans.size() << '\n';
    int n = ans.size();
    for (int i = 0; i < min(n, 1000); i++) {
        fout << ans[i] << ' ';
    }
    return 0;
}