博客

Boyer-Moore字符串匹配算法是一个在实践当中用得比较多的字符串查找算法，作者实现了一个C++版本的算法，供以后参考。

#include <iostream><br /> #include <algorithm><br /> #include <string><br /> #include <vector><br /> #ifndef ssize_t<br /> typedef off_t ssize_t;<br /> #endif<br /> using namespace std;<br /> void compute_last_occurrence(const string& needle , vector<ssize_t>& last_occurrence)<br /> {<br /> last_occurrence.resize(256,-1);<br /> for ( size_t i = 0 ; i < needle.size() ; i++ )<br /> {<br /> last_occurrence[needle[i]] = i;<br /> }<br /> }<br /> void compute_prefix_function(const string& needle , vector<size_t>& prefix_function)<br /> {<br /> if ( needle.size() == 0 )<br /> {<br /> return;<br /> }<br /> prefix_function.resize( needle.size() , 0 );<br /> size_t d = 0 ;<br /> for ( size_t i = 1 ; i < needle.size() ; i++ )<br /> {<br /> while ( d > 0 && needle[d] != needle[i] )<br /> {<br /> d = prefix_function[d-1];<br /> }<br /> if ( needle[i] == needle[d] )<br /> {<br /> d++;<br /> }<br /> prefix_function[i]=d;<br /> }<br /> }<br /> void compute_goodsuffix_heuristic( const string& needle ,vector<size_t>& goodsuffix_heristic)<br /> {<br /> string reverse_needle;<br /> copy( needle.rbegin() , needle.rend() , back_inserter( reverse_needle ) );<br /> vector<size_t> prefix_function,reverse_prefix_function;<br /> compute_prefix_function( needle , prefix_function );<br /> compute_prefix_function( reverse_needle , reverse_prefix_function );<br /> size_t m = needle.size();<br /> goodsuffix_heristic.resize( m + 1 , m – prefix_function[ m – 1 ] );<br /> for ( size_t l = 1 ; l <= m ; l++ )<br /> {<br /> size_t t = reverse_prefix_function[l-1];<br /> size_t j = m – t ;<br /> if ( goodsuffix_heristic[j] > l – t )<br /> {<br /> goodsuffix_heristic[j] = l – t ;<br /> }<br /> }<br /> }<br /> void boyer_moore_matcher(const string& haystack,const string& needle)<br /> {<br /> size_t n=haystack.size();<br /> size_t m=needle.size();<br /> if ( n == 0 || m == 0 || n < m )<br /> {<br /> cout<<“Invalid input”<<endl;<br /> return;<br /> }<br /> vector<ssize_t> last_occurrence;<br /> compute_last_occurrence(needle,last_occurrence);<br /> vector<size_t> goodsuffix_heristic;<br /> compute_goodsuffix_heuristic( needle , goodsuffix_heristic );<br /> size_t offset = 0 ;<br /> while ( offset <= n – m )<br /> {<br /> ssize_t j = m – 1 ;<br /> while ( j >= 0 && needle[j] == haystack[offset+j] )<br /> {<br /> j–;<br /> }<br /> if ( j < 0 )<br /> {<br /> cout<<“Find a match at offset “<<offset<<endl;<br /> offset += goodsuffix_heristic[0];<br /> }<br /> else<br /> {<br /> offset += max<size_t>( goodsuffix_heristic[j+1] ,<br /> j – last_occurrence[haystack[offset+j]] );<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> string haystack,needle;<br /> while ( true )<br /> {<br /> cout<<“Input the haystack:”<<endl;<br /> getline(cin,haystack);<br /> cout<<“Input the needle:”<<endl;<br /> getline(cin,needle);<br /> cout<<“Match results:”<<endl;<br /> boyer_moore_matcher(haystack,needle);<br /> }<br /> }<br />