Cod sursa(job #2409731)

Utilizator robx12lnLinca Robert robx12ln Data 19 aprilie 2019 12:56:20
Problema Potrivirea sirurilor Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.95 kb
#include<bits/stdc++.h>
using namespace std;

ifstream fin("strmatch.in");
ofstream fout("strmatch.out");

const int DIM = 2e6 + 10;

int P[DIM], Ans[DIM], Sol, L, N1, N2;
char S1[DIM], S2[DIM];
int main(){
    fin.getline( S1 + 1, DIM - 5 );
    fin.getline( S2 + 1, DIM - 5 );
    N1 = strlen( S1 + 1 );
    N2 = strlen( S2 + 1 );

    P[1] = 0;
    L = 0;
    for( int i = 2; i <= N1; i++ ){
        while( L != 0 && S1[L + 1] != S1[i] )
            L = P[L];
        if( S1[L + 1] == S1[i] )
            L++;
        P[i] = L;
    }

    L = 0;
    for( int i = 1; i <= N2; i++ ){
        while( L != 0 && S1[L + 1] != S2[i] )
            L = P[L];
        if( S1[L + 1] == S2[i] )
            L++;
        if( L == N1 ){
            Ans[++Sol] = i - N1;
            L = P[L];
        }
    }
    fout << Sol << "\n";
    Sol = min( Sol, 1000 );
    for( int i = 1; i <= Sol; i++ )
        fout << Ans[i] << " ";
    return 0;
}