Cod sursa(job #1813861)

Utilizator robx12lnLinca Robert robx12ln Data 23 noiembrie 2016 14:08:47
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<cstring>
#define DIM 2000005
using namespace std;
ifstream fin("strmatch.in");
ofstream fout("strmatch.out");
int n, m, P[DIM], nr, sol[1005], L;
char a[DIM], b[DIM];
int main(){
    fin >> a + 1;
    fin >> b + 1;
    n = strlen( a + 1 );
    m = strlen( b + 1 );
    //P[i] = lungimea celei mai lungi subsecventa a subsecventei 1...i care e prefix si sufix pentru ea
    // astefel incat prefixul si sufixul sa fie disjuncte
    L = 0;
    P[1] = 0;
    for( int i = 2; i <= n; i++ ){
        while( L != 0 && a[i] != a[L + 1] ){
            L = P[L];
        }
        if( a[i] == a[L + 1] ){
            L++;
        }
        P[i] = L;
    }
    L = 0;
    for( int i = 1; i <= m; i++ ){
        while( L != 0 && b[i] != a[L + 1] ){
            L = P[L];
        }
        if( b[i] == a[ L + 1] ){
            L++;
        }
        if( L == n ){
            L = P[L];
            nr++;
            if( nr <= 1000 ){
                sol[nr] = i - n;
            }
        }
    }
    fout << nr << "\n";
    for( int i = 1; i <= min(nr, 1000); i++ ){
        fout << sol[i] << " ";
    }
    return 0;
}