Cod sursa(job #3157199)

Utilizator pregoliStana Andrei pregoli Data 14 octombrie 2023 17:50:39
Problema Potrivirea sirurilor Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.37 kb
#include <bits/stdc++.h>
using namespace std;
const string FNAME = "strmatch";
ifstream fin(FNAME + ".in");
ofstream fout(FNAME + ".out");

vector<int> computeLPS(const string &s) {
    vector<int> lps(s.size());
    int j = 0;
    for (int i = 1; i < (int)s.size();) {
        if (s[i] == s[j]) {
            lps[i] = j + 1;
            j++, i++;
        } else {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }//*/
    return lps;
}

vector<int> computeKMP(const string &text, const string &pat) {
    vector<int> lps = computeLPS(pat), ans;
    const size_t n = text.size(), m = pat.size();
    size_t i = 0, j = 0;
    while (n - i >= m - j) {
        if (text[i] == pat[j]) {
            i++, j++;
        }
        if (j == m) {
            ans.push_back(i - j);
            j = lps[j - 1];
        } else if (text[i] != pat[j]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }
    return ans;
}

int main() {
    string pat, text;
    getline(fin, pat);
    getline(fin, text);
    vector<int> ans = computeKMP(text, pat);
    fout << ans.size() << endl;
    for (int x : ans) {
        fout << x << ' ';
    }
    fout << endl;
    return 0;
}