Cod sursa(job #2737111)

Utilizator trifangrobertRobert Trifan trifangrobert Data 4 aprilie 2021 14:14:34
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

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