BorderArray.h

Go to the documentation of this file.

 
#pragma once
 
#include <alib/vector>
#include <string/LinearString.h>
 
namespace string {
 
namespace properties {
 
class BorderArray {
public:
    template < class SymbolType >
    static ext::vector<size_t> construct(const string::LinearString < SymbolType >& string);
};
 
template < class SymbolType >
ext::vector<size_t> BorderArray::construct(const string::LinearString < SymbolType >& string) {
    const auto& w = string.getContent();
    ext::vector<size_t> res(w.size() + 1);
 
    res[0] = -1;
    if ( w.size ( ) > 0 )
        res[1] = 0;
 
    for(size_t i = 1; i < w.size(); i++) {
        size_t b = res[i];
        while (b > 0 && w[i] != w[b])
            b = res[b];
 
        if(w[i] == w[b])
            res[i + 1] = b + 1;
        else
            res[i + 1] = 0;
    }
 
    return res;
}
 
} /* namespace properties */
 
} /* namespace string */