Cod sursa(job #1974328)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 27 aprilie 2017 13:20:32
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <bits/stdc++.h>

using namespace std;
const int Nmax = 2000005;
char A[Nmax], B[Nmax];
int N, M;
int Pref[Nmax];

void make_prefix()
{
    int p = 0;
    for(int i = 2; i <= M; ++i) {
        while(p && B[i] != B[p + 1])
            p = Pref[p];
        p += (B[p + 1] == B[i]);
        Pref[i] =  p;
    }
}

void make_match()
{
    vector<int> sol;
    int cnt = 0;
    int p = 0;
    for(int i = 1; i <= N; ++i) {
        while(p && A[i] != B[p + 1])
            p = Pref[p];
        p += (B[p+1] == A[i]);
        if(p == M) {
            ++cnt;
            if(sol.size() < 1000) {
                sol.push_back(i - M);
            }
            p = Pref[p];
        }
    }
    cout << cnt << "\n";
    for(auto it : sol)
        cout << it << " ";
}

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

    cin >> (B+1);
    cin >> (A+1);
    A[0] = '#';
    B[0] = '#';
    N = strlen(A + 1);
    M = strlen(B + 1);

    make_prefix();
    make_match();



    return 0;
}