Cod sursa(job #2545101)

Utilizator MateiAruxandeiMateiStefan MateiAruxandei Data 12 februarie 2020 20:27:59
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

#define NMAX 2000005
using namespace std;

char A[NMAX], B[NMAX];
vector<int> v;

int pr[NMAX];

int main()
{
    ios_base::sync_with_stdio(0);
    freopen("strmatch.in", "r", stdin);
    freopen("strmatch.out", "w", stdout);

    cin.getline(A + 1, NMAX);
    cin.getline(B + 1, NMAX);

    int lg1 = strlen(A + 1), lg2 = strlen(B + 1);
    int k = 0;
    for(int i = 2; i <= lg1; ++i){
        while(k > 0 && A[k + 1] != A[i])
            k = pr[k];
        if(A[i] == A[k + 1])
            ++k;
        pr[i] = k;
    }

    k = 0;
    int cnt = 0;
    for(int i = 1; i <= lg2; ++i){
        while(k > 0 && A[k + 1] != B[i])
            k = pr[k];
        if(A[k + 1] == B[i])
            ++k;
        if(k == lg1){
            k = pr[lg1];
            if(v.size() < 1000)
                v.push_back(i - lg1);
            ++cnt;
        }
    }

    cout << cnt << '\n';
    for(auto it: v)
        cout << it << ' ';
    cout << '\n';
    return 0;
}