ExactEqual.h

Go to the documentation of this file.

 
#pragma once
 
#include <string/LinearString.h>
#include <string/CyclicString.h>
 
namespace string {
 
namespace naive {
 
class ExactEqual {
public:
    template < class SymbolType >
    static bool equals(const string::LinearString < SymbolType >& u, const string::LinearString < SymbolType >& v);
 
    template < class SymbolType >
    static bool equals(const string::CyclicString < SymbolType >& u, const string::CyclicString < SymbolType >& v);
};
 
template < class SymbolType >
bool ExactEqual::equals ( const string::LinearString < SymbolType > & u, const string::LinearString < SymbolType > & v ) {
    size_t n = u.getContent ( ).size ( );
    size_t m = v.getContent ( ).size ( );
    size_t k = 0;
 
    while ( k < n && k < m && u.getContent ( )[k] == v.getContent ( )[k] ) k++;
 
    if ( ( k == m ) && ( k == n ) )
        return true;
    else
        return false;
}
 
template < class SymbolType >
bool ExactEqual::equals ( const string::CyclicString < SymbolType > & u, const string::CyclicString < SymbolType > & v ) {
    size_t n = u.getContent ( ).size ( );
    size_t i = 0;
    size_t j = 0;
 
    if ( n != v.getContent ( ).size ( ) )
        return false;
 
    while ( i < n && j < n ) {
        size_t k = 0;
 
        while ( k < n && u.getContent ( )[( i + k ) % n] == v.getContent ( )[( j + k ) % n] ) k++;
 
        if ( k >= n ) return true;
 
        if ( u.getContent ( )[( i + k ) % n] > v.getContent ( )[( j + k ) % n] )
            i += k + 1;
        else
            j += k + 1;
    }
 
    return false;
}
 
} /* namespace naive */
 
} /* namespace string */