Cod sursa(job #3286505)

Utilizator Alex_DumitrascuAlex Dumitrascu Alex_Dumitrascu Data 14 martie 2025 12:02:25
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 2000005;
string pat, str;
int lsp[MAXN];
vector<int> sol;

void precompute_lsp() {
    int m = pat.size();
    lsp[0] = 0;
    int len = 0;

    for (int i = 1; i < m; i++) {
        while (len > 0 && pat[i] != pat[len]) {
            len = lsp[len - 1];  // Backtrack
        }
        if (pat[i] == pat[len]) {
            len++;
        }
        lsp[i] = len;
    }
}

void kmp() {
    int n = str.size(), m = pat.size();
    int j = 0;  // Index for pat

    for (int i = 0; i < n; i++) {
        while (j > 0 && str[i] != pat[j]) {
            j = lsp[j - 1];  // Backtrack
        }
        if (str[i] == pat[j]) {
            j++;
        }
        if (j == m) {  // Found a match
            if (sol.size() < 1000) sol.push_back(i - m + 1);
            j = lsp[j - 1];  // Continue searching
        }
    }
}

int main() {
    fin >> pat >> str;

    precompute_lsp();
    kmp();

    fout << sol.size() << '\n';
    for (int s : sol) fout << s << ' ';

    return 0;
}