Cod sursa(job #3153466)

Utilizator trifangrobertRobert Trifan trifangrobert Data 29 septembrie 2023 18:55:07
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.84 kb
#include <fstream>
#include <vector>
#include <string>

using namespace std;

int main() {
    ifstream fin("strmatch.in");
    ofstream fout("strmatch.out");
    string s, t;
    fin >> s >> t;
    int N = s.length();
    s = s + "$" + t;
    vector <int> pi(s.length(), 0);
    for (int i = 1, k = 0;i < s.length();++i) {
        while (k > 0 && s[i] != s[k]) {
            k = pi[k - 1];
        }
        if (s[i] == s[k]) {
            k += 1;
        }
        pi[i] = k;
    }
    vector <int> answer;
    int cnt = 0;
    for (int i = 0;i < pi.size();++i) {
        if (pi[i] == N) {
            cnt += 1;
            if (cnt <= 1000) {
                answer.push_back(i - 2 * N);
            }
        }
    }
    fout << cnt << "\n";
    for (auto& x : answer) {
        fout << x << " ";
    }
    fin.close();
    fout.close();
    return 0;
}