From Gossip@caterpillar

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++) 
        tmp[j] = text[i]; 

    tmp[j] = '\0'; 
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringMatch {
    private int[] skip;
    private int p;
    private String str;
    private String key;
    
    public StringMatch(String key) {
        skip = new int[256];
        this.key = key;
        
        for(int k = 0; k <= 255; k++) 
            skip[k] = key.length(); 
        for(int k = 0; k < key.length() - 1; k++) 
            skip[key.charAt(k)] = key.length() - k - 1; 
    }
    
    public void search(String str) {
        this.str = str;
        p = search(key.length()-1, str, key);
    }
    
    private int search(int p, String input, String key) {   
        while(p < input.length()) { 
            String tmp = input.substring(
                                p-key.length()+1, p+1); 

            if(tmp.equals(key))  // 比較兩字串是否相同 
               return p-key.length()+1; 
            p += skip[input.charAt(p)]; 
        } 

        return -1; 
    }
    
    public boolean hasNext() {
        return (p != -1);
    }
    
    public String next() {
        String tmp = str.substring(p);
        p = search(p+key.length()+1, str, key);
        return tmp;
    }
    
    public static void main(String[] args) 
                                      throws IOException {
        BufferedReader bufReader = 
            new BufferedReader(
                    new InputStreamReader(System.in));
        
        System.out.print("請輸入字串：");
        String str = bufReader.readLine();
        System.out.print("請輸入搜尋關鍵字："); 
        String key = bufReader.readLine();
        
        StringMatch strMatch = new StringMatch(key);
        strMatch.search(str);

        while(strMatch.hasNext()) { 
            System.out.println(strMatch.next()); 
        } 
    }
}