Cod sursa(job #1503732)

Utilizator jimcarterJim Carter jimcarter Data 16 octombrie 2015 20:30:10
Problema Potrivirea sirurilor Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.6 kb
#include <iostream>
#include <fstream>
#include <cstdio>
#include <string>
#include <vector>
using namespace std;
ifstream f ( "strmatch.in" );

const int MAX = 2000005;
string X , S;
int longps [ MAX ] , i , Xlen , Slen , N , pref;
vector <int> matches;

void read()
{
    getline ( f , X );
    //set length
    X = ' ' + X;
    Xlen = X.size();

    getline ( f , S );
    //set length
    S = ' ' + S;
    Slen = S.size();
}

void prefix_suffix()
{
    pref = 0;
    longps [ 0 ] = -1;
    longps [ 1 ] = 0;

    for ( i = 2 ; i < Xlen ; i++ )
    {
        pref = longps [ i - 1 ];

        while ( pref >= 0 && X [ pref + 1 ] != X [ i ] )
            pref = longps [ pref ];

        longps [ i ] = pref + 1;
    }
}

void KMP()
{
    pref = 0;
    for ( i = 1 ; i < Slen ; i++ )
    {
        while ( pref > 0 && S [ i ] != X [ pref + 1 ] )
            pref = longps [ pref ];

        if ( S [ i ] == X [ pref + 1 ] )
            pref ++;

        if ( pref == Xlen - 1 )
        {
            pref = longps [ pref ];
            N ++;
            if ( N <= 1000 )
                matches.push_back ( i - Xlen + 1 );
        }

    }
}

void print()
{
    printf ( "%d\n" , N );
    N = min ( N , 1000 );
    for ( i = 0 ; i < N ; i ++ )
        printf ( "%d " , matches [ i ] );
    printf ( "\n" );
}

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

    read();

    //find the longest prefix that's also a suffix in X
    prefix_suffix();

    //search for string matches by moving X according to longps
    KMP();

    print();
}