Cod sursa(job #1790696)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 28 octombrie 2016 17:02:50
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.01 kb
#include <bits/stdc++.h>

using namespace std;
const int Nmax = 2000005;
vector<int> sol;
char A[Nmax],B[Nmax];
int P[Nmax], N, M, total;

void make_prefix()
{
    int q = 0;
    for(int i = 2; i <= N; ++i) {
        while(q && A[q + 1] != A[i])
            q = P[q];
        q += A[q+1] == A[i];
        P[i] = q;
    }
}

void make_match()
{
    int q = 0;
    for(int i = 1; i <= M; ++i) {
        while(q && A[q + 1] != B[i])
            q = P[q];
        q += A[q+1] == B[i];
        if(q == N) {
            q = P[q];
            ++total;
            if(total <= 1000) {
                sol.push_back(i - N);
            }
        }
    }
}

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

    scanf("%s", A + 1); A[0] = '#'; N = strlen(A + 1);
    scanf("%s", B + 1); B[0] = '#'; M = strlen(B + 1);

    make_prefix();
    make_match();

    cout << total << "\n";
    for(auto it : sol)
        cout << it << " ";

    return 0;
}