Cod sursa(job #2737122)

Utilizator trifangrobertRobert Trifan trifangrobert Data 4 aprilie 2021 14:22:29
Problema Potrivirea sirurilor Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 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> z(s.length(), 0);
    for (int i = 1, left = 0, right = 0; i < s.length(); ++i) {
        if (i > right) {
            left = right = i;
            while (right < s.length() && s[right] == s[right - left])
                ++right;
            z[i] = right - left;
            --right;
        }
        else {
            if (i + z[i - left] + 1 < right) {
                z[i] = z[i - left];
            }
            else {
                left = i;
                while (right < s.length() && s[right] == s[right - left])
                    ++right;
                z[i] = right - left;
                --right;
            }
        }
    }
    int cnt = 0;
    vector <int> answer;
    for (int i = szS; i < s.length(); ++i) {
        if (z[i] == szS) {
            ++cnt;
            if (answer.size() < 1000) {
                answer.push_back(i - szS - 1);
            }
        }
    }
    fout << cnt << "\n";
    for (auto& i : answer)
        fout << i << " ";
    fin.close();
    fout.close();
    return 0;
}