算法题字符串匹配算法

1. 传统的字符串匹配算法

传统匹配思想是，从目标串Target的第一个字符开始扫描，逐一与模式串的对应字符进行匹配，若该组字符匹配，则检测下一组字符，如遇失配，则退回到Target的第二个字符，重复上述步骤，直到整个Pattern在Target中找到匹配，或者已经扫描完整个目标串也没能够完成匹配为止。

这种算法的就是包括两个循环, 设Target串的长度是n, Pattern串的长度是m, 那么复杂度是O(m*n)

参考代码:

void NativeStrMatching( ElemType Target[], ElemType Pattern[] )
{
    register int TarLen = 0; // Length of Target
    register int PatLen = 0; // Length of Pattern
    // Compute the length of Pattern
    while( '\0' != Pattern[PatLen] )
        PatLen++;
    while( '\0' != Target[TarLen] )
    {
        int TmpTarLen = TarLen;
        for(int i=0; i<PatLen; i++)
        {
            if( Target[TmpTarLen++] != Pattern[i] )
                break;
            if( i == PatLen-1 )
                cout<<"Native String Matching,pattern occurs with shift "<<TarLen<<endl;
        }
        TarLen++;
    }
}

C++代码:

void NativeStrMatch(const string& target,const string& pattern){
    int n=target.size();
    int m=pattern.size();
    for(int i=0;i<n;i++){
        int k=i;
        int j;
        for(j=0;j<m&&target[k]==pattern[j];k++,j++)
            ;
        if(j==m){
            cout<<"Native string Matching occurs at "<<i<<endl;
        }
    }
}

2. KMP算法

传统算法虽然简单易行，但其中包含了过多的不必要操作，并不能很好地达到实际工作中需要的效率.

KMP算法就能很好地解决这个冗余问题。

其主要思想为：

在失配后，并不简单地从目标串下一个字符开始新一轮的检测，而是依据在检测之前得到的有用信息（稍后详述），直接跳过不必要的检测，从而达到一个较高的检测效率。

KMP算法主要包括计算前缀数组以及利用这个前缀数组进行判断.

前缀计算的参考代码:

// Compute Prefix function
void CptPfFunc( ElemType Pattern[], int PrefixFunc[] )
{
    register int iLen = 0; // Length of Pattern[]
    while( '\0' != Pattern[iLen] )
        iLen++;
    int LOLP = 0; // Lenth of longest prefix
    PrefixFunc[1] = 0;
    for( int NOCM=2; NOCM<iLen+1; NOCM++ ) // NOCM represent the number of characters matched
    {
        while( LOLP>0 && (Pattern[LOLP] != Pattern[NOCM-1]) )
            LOLP = PrefixFunc[LOLP];
        if( Pattern[LOLP] == Pattern[NOCM-1] )
            LOLP++;
        PrefixFunc[NOCM] = LOLP;
    }
}

利用前缀进行匹配的KMP算法参考代码:

void KMPstrMatching( ElemType Target[], ElemType Pattern[] )
{
    int PrefixFunc[MAX_SIZE];
    register int TarLen = 0;
    register int PatLen = 0;
    // Compute the length of array Target and Pattern
    while( '\0' != Target[TarLen] )
        TarLen++;
    while( '\0' != Pattern[PatLen] )
        PatLen++;
    // Compute the prefix function of Pattern
    CptPfFunc( Pattern, PrefixFunc );
    int NOCM = 0; // Number of characters matched
    for( int i=0; i<TarLen; i++ )
    {
        while( NOCM>0 && Pattern[NOCM] != Target[i] )
            NOCM = PrefixFunc[NOCM];
        if( Pattern[NOCM] == Target[i] )
            NOCM++;
        if( NOCM == PatLen )
        {
            cout<<"KMP String Matching,pattern occurs with shift "<<i - PatLen + 1<<endl;
            NOCM = PrefixFunc[NOCM];
        }
    }
}

完整的KMP算法对应的C++代码如下:

#include <iostream>
#include <string>
using namespace std;
//compute prefix function
void CptPfFunc(const string& pattern,int* prefix){
    size_t m=pattern.size();
    int j=0;//length of longest prefix
    prefix[1]=0;
    for(int i=2;i<=m;i++){
        while(j>0&&pattern[j]!=pattern[i-1])
            j=prefix[j];
        if(pattern[j]==pattern[i-1])
            j++;
        prefix[i]=j;
    }
}
void KMPstrMatch(const string& target,const string& pattern){
    int n=target.size();
    int m=pattern.size();
    int *prefix=new int[m+1];
    CptPfFunc(pattern,prefix);
    int j=0;
    for(int i=0;i<n;i++){
        while(j>0&&pattern[j]!=target[i])
            j=prefix[j];
        if(pattern[j]==target[i])
            j++;
        if(j==m){
            cout<<"KMP string Matching occurs at "<<i-j+1<<endl;
            j=prefix[j];
        }
    }
    delete [] prefix;
}

参考:

http://billhoo.blog.51cto.com/2337751/411486

http://www.matrix67.com/blog/archives/115/

11.Algorithm Gossip: 字符串核对

说明今日的一些高阶程序语言对于字符串的处理支持越来越强大（例如Java、Perl等），不过字符串搜寻本身仍是个值得探讨的课题，在这边以Boyer- Moore法来说明如何进行字符串说明，这个方法快且原理简洁易懂。

解法字符串搜寻本身不难，使用暴力法也可以求解，但如何快速搜寻字符串就不简单了，传统的字符串搜寻是从关键字与字符串的开头开始比对，例如 Knuth-Morris-Pratt 算法字符串搜寻，这个方法也不错，不过要花时间在公式计算上；Boyer-Moore字符串核对改由关键字的后面开始核对字符串，并制作前进表，如果比对不符合则依前进表中的值前进至下一个核对处，假设是p好了，然后比对字符串中p-n+1至p的值是否与关键字相同。

那麼前進表該如何前進，舉個實際的例子，如果要在字串中搜尋JUST這個字串，則可能遇到的幾個情況如下所示：

依照這個例子，可以決定出我們的前進值表如下：

其它	J	U	S	T
4	3	2	1	4（match?）

如果关键字中有重复出现的字符，则前进值就会有两个以上的值，此时则取前进值较小的值，如此就不会跳过可能的位置，例如texture这个关键字，t的前进值应该取后面的3而不是取前面的7。

#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
void table(char*); // 建立前进表
int search(int, char*, char*); // 搜寻关键字
void substring(char*, char*, int, int); // 取出子字符串
int skip[256]; 
int main(void) { 
    char str_input[80]; 
    char str_key[80]; 
    char tmp[80] = {'\0'}; 
    int m, n, p; 
    printf("请输入字符串："); 
    gets(str_input); 
    printf("请输入搜寻关键字："); 
    gets(str_key); 
    m = strlen(str_input); // 计算字符串长度
    n = strlen(str_key); 
    table(str_key); 
    p = search(n-1, str_input, str_key); 
    while(p != -1) { 
        substring(str_input, tmp, p, m); 
        printf("%s\n", tmp); 
        p = search(p+n+1, str_input, str_key); 
    } 
    printf("\n"); 
    return 0; 
} 
void table(char *key) { 
    int k, n; 
    n = strlen(key); 
    for(k = 0; k <= 255; k++) 
        skip[k] = n; 
    for(k = 0; k < n - 1; k++) 
        skip[key[k]] = n - k - 1; 
} 
int search(int p, char* input, char* key) { 
    int i, m, n; 
    char tmp[80] = {'\0'}; 
    m = strlen(input); 
    n = strlen(key); 
    while(p < m) { 
        substring(input, tmp, p-n+1, p); 
        if(!strcmp(tmp, key)) // 比较两字符串是否相同
            return p-n+1; 
        p += skip[input[p]]; 
    } 
    return -1; 
} 
void substring(char *text, char* tmp, int s, int e) { 
    int i, j; 
    for(i = s, j = 0; i <= e; i++, j++) 
        mp[j] = text[i]; 
    tmp[j] = '\0'; 
}