4
\$\begingroup\$

First of all, I know there is huge amount of information about KMP on the internet but many examples are just the code without any explanation. So I've decided to implement it on my own.

Secondly, I am going to use this algorithm to search for a pattern in a numerical string.

I wrapped all the stuff in class KMP.

CODE

KMP.h

#ifndef KMP_H
#define KMP_H

#include <cstddef>
#include <vector>


class KMP
{
    protected :
        std::vector< size_t > found_positions;


    public :
        KMP() :
            found_positions( 0 )
        { }

        void build_failure_vector( const std::vector< float >& pattern,
                                   std::vector< int >& failure_vector );

        void search_for_pattern( const std::vector< float >& pattern,
                                 const std::vector< float >& sample );

        typedef typename std::vector< size_t >::const_iterator position_iterator; 
        inline position_iterator cbegin() const noexcept { return found_positions.cbegin(); }
        inline position_iterator cend() const noexcept { return found_positions.cend(); }

};


#endif

KMP.cpp

#include "KMP.h"


void KMP::build_failure_vector( const std::vector< float >& pattern,
                                std::vector< int >& failure_vector )
{
    //extra space for the case when all occurencies are required
    failure_vector.resize( pattern.size() + 1 );

    //set -1 as an indicator of the beginning of a pattern
    failure_vector[ 0 ] = -1;

    //in the case of a mismatch we don't shift text index back
    //but instead we check if we could proceed from a proper suffix of the pattern 
    //it is the pattern index which indicates the position of a potential match
    int continue_from;

    for( size_t i = 1; i < failure_vector.size(); i++ )
    {
        //if a mismatch was at index i
        //we check if the beginning of a pattern has been reached or
        //the previous pattern character (at i-1) matches
        //some failure character

        //start from the failure at the previous pattern index 
        continue_from = failure_vector[ i-1 ];

        while( (continue_from >= 0)  &&
               (pattern[ continue_from ] != pattern[ i-1 ] ) )
        {
            continue_from = failure_vector[ continue_from ];
        }

        //if in the above while loop we found that
        //pattern[ i-1 ] == pattern[ continue_from ] for some continue_from index
        //then we should check if the current main text character mathes pattern[ continue_from + 1 ]
        failure_vector[ i ] = continue_from + 1;
    }
}


void KMP::search_for_pattern( const std::vector< float >& pattern,
                              const std::vector< float >& sample )
{
    //prepare failure function
    std::vector< int > failure_vector;
    build_failure_vector( pattern, failure_vector );
    //position in the main text
    size_t sample_pos = 0;
    //must be of type int because may be equal to -1
    int    pattern_pos = 0;

    while( sample_pos < sample.size() ) 
    {
        //check next character in the main text
        //only if the next potential match is the beginning of the pattern
        //or there is a match
        if( (pattern_pos < 0)  ||
            (sample[ sample_pos ] == pattern[ pattern_pos ]) )
        {
            sample_pos++;
            //if pattern_pos was -1 then it becomes 0
            //i.e. we start from the beginning
            pattern_pos++;

            if( pattern_pos == pattern.size() )
            {
                //complete match occured
                found_positions.push_back( sample_pos - pattern_pos ); 
                //the last position in failure_vector
                //says what we should continue from after complete match
                pattern_pos = failure_vector[ pattern_pos ];
            }
        }
        //if there was a mismatch
        else
        {
            //what next character of the pattern is a potential match
            pattern_pos = failure_vector[ pattern_pos ];
        }
    }
}

Usage

Usage is straightforward. For example,

Sample vector: [ 3, 1, 3, 1, 3, 2, 0, 1, 3, 1, 3, ]

Pattern vector: [ 3, 1, 3, ]

Failure vector: [ -1, 0, 0, 1, ]

Pattern found positions vector: [ 0, 2, 8, ]

\$\endgroup\$
3
\$\begingroup\$

Let the Compiler do the Optimization
C++ compilers have become very good at optimization, especially when they are compiled -O3. The compiler will handle optimizations such as inlining functions automatically, there is no need for the inline specification preceding functions in header files. See this stack overflow question.

It isn't apparent that the functions cbegin() and cend() are ever used in the code.

Including Unnecessary Header Files
The code compiles properly without including cstddef. Including unnecessary header files may introduce symbol collisions, it also slows down compile times because the code in the include file needs to compiled as well.

Over Commenting
It is obvious that commenting the solution is one of the main goals, and that is a good goal, however, there is such a thing as over commenting code. As code ages there will be changes to it to fix bugs or for optimization and comments require extra work to make sure they continue to represent the code. It is best to use variable and function names that are self documenting to make the code clearer. If the algorithm need commenting, it might be better to put a block comment at the top of the function.

\$\endgroup\$
  • \$\begingroup\$ Oh, cbegin() and cend() are used in the usage stage. I just omitted main(). They are for iterating over found positions. BTW. What's wrong with inlining functions in header files? I am using YouCompleteMe plugin and without cstddef header it complained that size_t was unknown type. \$\endgroup\$ – LRDPRDX Apr 26 at 4:22
  • \$\begingroup\$ @LRDPRDX Since main() wasn't included and no link was provided to all source code I could only review what was here, therefore the cstddef header is not necessary nor is cbegin and cend. I've added a link to stack overflow about why you shouldn't use the inline keyword any more. If you look at my first question on code review you'll find that I did use it as well. \$\endgroup\$ – pacmaninbw Apr 26 at 11:16
  • \$\begingroup\$ @LRDPRDX & pacmaninbw: Functions defined in the class are automatically inline. This has little to do with optimization. \$\endgroup\$ – L. F. Apr 27 at 1:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.