Cod sursa(job #1920008)

Utilizator blatulInstitutul de Arta Gastronomica blatul Data 9 martie 2017 22:00:41
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.12 kb
#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 2000000;

char A[2 * kMaxN + 2], B[kMaxN + 1];
int Z[2 * kMaxN + 1];

int main() {
    #ifdef INFOARENA
    ifstream cin("strmatch.in");
    ofstream cout("strmatch.out");
    #endif
    cin.tie(0);
    ios_base::sync_with_stdio(false);
    
    cin >> A >> B;
    int n = strlen(A);
    A[n] = '#';
    memcpy(A + n + 1, B, sizeof B);
    
    int st = 0, fn = 0;
    int stringSize = n + 1 + strlen(B);
    for(int i = 1; i < stringSize; ++i) {
        if(i <= fn) Z[i] = min(Z[i - st], fn - i + 1);
            
        while(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;
    answer.reserve(1000);
    for(int i = n + 1; i < stringSize; ++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';
}