字符串匹配算法

ÓÃÓïÑÔʵÏÖÂùÁ¦·¨¡¢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() { }

#include using namespace std;

const int HASH_SIZE=256;

string a = \"abcdefg\"; string mode = \"z\";

cout<int

table[HASH_SIZE];//¶ÔÓ¦×Ö·û±íµÄ255¸ö×Ö·û½¨¹þÏ£±í,±íʾ¶Ô²»Æ¥Åä×Ö·û ÏòÓÒÒƶ¯µÄ¾àÀë

void ShiftTable(char pattern[]){

/*½¨Á¢Ò»¸öÒÔ×Öĸ±íÖÐ×Ö·ûΪË÷ÒýµÄTableÊý×é*/ int m=strlen(pattern); for(int i=0;ifor(int j=0;jint HorspoolMatching(char pattern[],char text[]){//ƽ¾ùЧÂÊΪO(n) /*

pre:ģʽpattern£¬Îı¾text

post:µÚÒ»¸öÆ¥Åä×Ö´®µÄ×î×ó¶Ë×Ö·ûϱ꣬ûÓÐÕÒµ½Æ¥Åä×Ö´®·µ»Ø-1 */

ShiftTable(pattern); int m=strlen(pattern); int n=strlen(text);

int i=m-1;

while(i <= n-1){

int k=0; //Æ¥ÅäµÄ×Ö·û¸öÊý

while(k<=m-1 && pattern[m-1-k] == text[i-k] ) k++; if(k==m)

return i-m+1; else

i=i+table[

text[i]

];

//ÒÔģʽ×îºóÒ»¸ö×Ö·ûÈ·¶¨Òƶ¯¾àÀë,ÓëB.MËã·¨µÄ×î´óÇø±ð£¬¼ò»¯ÐÎʽ }

return -1; }

int main(){

char p[20],t[1000];

while(cin>>t && t!=\".\"){

int times=5; while(times--){ cin>>p;

cout<}

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_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 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

,

string&

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\"<}

vector 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 \"<{

offset += max( goodsuffix_heristic[j+1] , j - last_occurrence[haystack[offset+j]] ); } } }

int main()

{

string haystack,needle;

while ( true ) {

cout<<\"Input the haystack:\"<cout<<\"Input the needle:\"<cout<<\"Match results:\"<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 int[len];

int i = 0;

int j = -1; next[0] = -1;

while(iif(j==-1 || s[i]==s[j]) { ++i; ++j;

next[i] = j; } else

{

j = next[j]; } }

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(iif(j==-1 || s[i]==t[j]) {

++i; ++j; } else {

j = next[j]; } }

delete[] next;

if(j==tlen)

return i - tlen;

return -1;

}

int main(int argc, char *argv[]) {

char s[128],t[128];

cout<<\"ÇëÊäÈë×Ö·û´®s,t:\"<>s>>t)

{

int pos1 = KMP(s,t);

cout<<\"×Ö·û´®\"<return 0; }