Cod sursa(job #2976752)

Utilizator indianu_talpa_iuteTisca Catalin indianu_talpa_iute Data 9 februarie 2023 22:41:53
Problema Potrivirea sirurilor Scor 14
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.06 kb
#include <bits/stdc++.h>
#define MAXSZ 100

using namespace std;

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

int n, m, lps[MAXSZ + 1];
char a[MAXSZ + 1], b[MAXSZ + 1];

void computeLPS() {
    int length = 0;
    lps[0] = 0;
    for (int i = 1; i < n; i++) {
        while (length > 0 && a[length] != a[i])
            length = lps[length];
        if (a[length] == a[i]) {
            lps[i] = length++;
            continue;
        }
        lps[i] = length;
    }
}

vector<int> findMatches() {
    vector<int> matches;
    int j = 0;
    for (int i = 0; i < m; i++) {
        while (j > 0 && a[j + 1] != b[i])
            j = lps[j];
        if (a[j + 1] == b[i])
            j++;
        if (j == n - 1)
            matches.push_back(i - n + 1);
    }

    return matches;
}

int main() {
    fin.getline(a, MAXSZ);
    fin.getline(b, MAXSZ);
    n = (int) strlen(a);
    m = (int) strlen(b);
    computeLPS();
    vector<int> matches = findMatches();
    fout << matches.size() << '\n';
    for (auto& match: matches)
        fout << match << ' ';
    return 0;
}