字符串匹配算法.doc

3HorspoolBoyer-MooreKnuth-Morris-Pratt100000int BruteForceStringMatch(string str, string pattern)for( int i = 0; i = str.size()- pattern.size(); i+ )int j = 0;while( (j pattern.size() & (patternj = stri+j)j+;if( j = pattern.size()return i;return (-1);void ShiftTable(string pattern, int table, int l)for(int i = 0; i 127; i+)tablei = l;for(int j = 0; j l-1; j+)tablepatternj = l-1-j;void HorspoolMatch(string str, int table, string pSize)int main()string a = abcdefg;string mode = z;coutBruteForceStringMatch(a, mode)endl;return 0;#includeusing namespace std;const int HASH_SIZE=256;int tableHASH_SIZE;/255, void ShiftTable(char pattern)/*Table*/int m=strlen(pattern);for(int i=0;iHASH_SIZE;i+) tablei=m;for(int j=0;jm-1;j+) table patternj =m-1-j;int HorspoolMatching(char pattern,char text)/O(n)/*pre:patterntextpost:-1*/ShiftTable(pattern);int m=strlen(pattern);int n=strlen(text);int i=m-1;while(i = n-1) int k=0; / while(kt & t!=.) int times=5; while(times-) cinp; coutHorspoolMatching(p,t)endl; return 1; #include #include #include #include #ifndef ssize_t typedef off_t ssize_t; #endif using namespace std; void compute_last_occurrence(const string& needle , vector& last_occurrence) last_occurrence.resize(256,-1); for ( size_t i = 0 ; i needle.size() ; i+ ) last_occurrenceneedlei = i; void compute_prefix_function(const string& needle , vector& prefix_function) if ( needle.size() = 0 ) return; prefix_function.resize( needle.size() , 0 ); size_t d = 0 ; for ( size_t i = 1 ; i 0 & needled != needlei ) d = prefix_functiond-1; if ( needlei = needled ) d+; prefix_functioni=d; void compute_goodsuffix_heuristic( const string& needle ,vector& goodsuffix_heristic) string reverse_needle; copy( needle.rbegin() , needle.rend() , back_inserter( reverse_needle ) ); vector prefix_function,reverse_prefix_function; compute_prefix_function( needle , prefix_function ); compute_prefix_function( reverse_needle , reverse_prefix_function ); size_t m = needle.size(); goodsuffix_heristic.resize( m + 1 , m - prefix_function m - 1 ); for ( size_t l = 1 ; l l - t ) goodsuffix_heristicj = l - t ; void boyer_moore_matcher(const string& haystack,const string& needle) size_t n=haystack.size(); size_t m=needle.size(); if ( n = 0 | m = 0 | n m ) coutInvalid inputendl; return; vector last_occurrence; compute_last_occurrence(needle,last_occurrence); vector goodsuffix_heristic; compute_goodsuffix_heuristic( needle , goodsuffix_heristic ); size_t offset = 0 ; while ( offset = 0 & needlej = haystackoffset+j ) j-; if ( j 0 ) coutFind a match at offset offsetendl; offset += goodsuffix_heristic0; else offset += max( goodsuffix_heristicj+1 , j - last_occurrencehaystackoffset+j ); int main() string haystack,needle; while ( true ) coutInput the haystack:endl; getline(cin,haystack); coutInput the needle:endl; getline(cin,needle); coutMatch results:endl; boyer_moore_matcher(haystack,needle); #include #include #include #include using namespace std; int* GetNextVal(const char *s, int &len) len = strlen(s); int *next = new intlen; int i = 0; int j = -1; next0 = -1; while(ilen-1)/KMP if(j=-1 | si=sj) +i; +j; nexti = j; else j = nextj; return next; int KMP(const char *s, const char *t) int slen,tlen; int i,j; int *next = GetNextVal(t, tlen); slen = strlen(s); i = 0; j = 0; while(islen & jtlen) if(j=-1 | si=tj) +i; +j; el