Cod sursa(job #1503656)

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

const int MAX = 2000001;
string X , S;
int longps [ MAX ] , i , Xlen , Slen , Xi , Si;
vector <int> matches;

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

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

void prefix_suffix()
{
    int pref = 0;
    longps [ 0 ] = 0;
    for ( i = 1 ; i < Xlen ; i ++ )
        if ( X [ i ] == X [ pref ] )
        {
            longps [ i ] = longps [ i - 1 ] + 1;
            pref ++;
        }
        else
        {
            longps [ i ] = 0;
            pref = 0;
        }
}

void KMP()
{
    int Xi = 0;
    for ( Si = 0 ; Si < Slen ; Si ++ )
        if ( S [ Si ] == X [ Xi ] )
        {
            //set the new length
            Xi ++;
            if ( Xi == Xlen )
            {
                matches.push_back( Si - Xlen + 1 );
                Xi = longps [ Xi - 1 ];
            }
        }
        else
        {
            //set the new length
            Xi = 0;
            if ( X [ Xi ] == S [ Si ] )
                Si --;
        }
}

void print()
{
    int N = matches.size();
    printf ( "%d\n" , N );
    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();
}