Cod sursa(job #1919985)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 9 martie 2017 21:52:39
Problema Potrivirea sirurilor Scor 80
Compilator cpp Status done
Runda Arhiva educationala Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;

int main() {
    #ifdef INFOARENA
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);
    #endif
   
    string A, B;
    cin >> A >> B;
    int n = A.size();
    
    A = A + '#' + B;
    
    vector<int> Z(A.size());
    int st = 0, fn = 0;
    for(int i = 1; i < (int)A.size(); ++i) {
        if(i <= fn) Z[i] = min(Z[i - st], fn - i + 1);
            
        while(i + Z[i] < (int)A.size() && A[i + Z[i]] == A[Z[i]])
            ++Z[i];
            
        if(i + Z[i] - 1 > fn) {
            fn = i + Z[i] - 1;
            st = i;
        }
    }
    
    int answerCount = 0;
    vector<int> answer;
    for(int i = n + 1; i < (int)A.size(); ++i)
        if(Z[i] == n) {
            answerCount++;
            
            if(answerCount <= 1000)
                answer.push_back(i - n - 1);
        }
    
    cout << answerCount << '\n';
    for(const int& x: answer)
        cout << x << ' ';
    cout << '\n';
}