[宝典]字符串匹配算法下载_Word模板_11

[宝典]字符串匹配算法字符串匹配算法用语言实现蛮力法、Horspool、Boyer-Moore、Knuth-Morris-Pratt算法，针对不同的数据规模研究它们的性能。数据规模应在100，000 以上。 int BruteForceStringMatch(string str, string pattern) { for( int i = 0; i <= str.size()- pattern.size(); i++ ) { int j = 0; while( (j < pattern.size()) && (pattern[j] == str[i+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++) table[i] = l; for(int j = 0; j < l-1; j++) table[pattern[j]] = l-1-j; } void HorspoolMatch(string str, int table[], string pSize) int main() { string a = "abcdefg"; string mode = "z"; cout< using namespace std; const int HASH_SIZE=256; int table[HASH_SIZE];//对应字符表的255个字符建哈希表,表示对不匹配字符向右移动的距离 void ShiftTable(char pattern[]){ /*建立一个以字母表中字符为索引的Table数组*/ int m=strlen(pattern); for(int i=0;i>t && t!="."){ int times=5; while(times--){ cin>>p; cout< #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_occurrence[needle[i]] = 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 < needle.size() ; i++ ) { while ( d > 0 && needle[d] != needle[i] ) { d = prefix_function[d-1]; } if ( needle[i] == needle[d] ) { d++; } prefix_function[i]=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 <= m ; l++ ) { size_t t = reverse_prefix_function[l-1]; size_t j = m - t ; if ( goodsuffix_heristic[j] > l - t ) { goodsuffix_heristic[j] = 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 ) { cout<<"Invalid input"< last_occurrence; compute_last_occurrence(needle,last_occurrence); vector goodsuffix_heristic; compute_goodsuffix_heuristic( needle , goodsuffix_heristic ); size_t offset = 0 ; while ( offset <= n - m ) { ssize_t j = m - 1 ; while ( j >= 0 && needle[j] == haystack[offset+j] ) { j--; } if ( j < 0 ) { cout<<"Find a match at offset "<( goodsuffix_heristic[j+1] , j - last_occurrence[haystack[offset+j]] ); } } } int main() { string haystack,needle; while ( true ) { cout<<"Input the haystack:"< #include #include #include using namespace std; int* GetNextVal(const char *s, int &len) { len = strlen(s); int *next = new int[len]; int i = 0; int j = -1; next[0] = -1; while(i>s>>t) { int pos1 = KMP(s,t); cout<<"字符串"<

                    本文档为【[宝典]字符串匹配算法】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

[宝典]字符串匹配算法

你可能还喜欢