資料結構與算法（32）——字元串算法

檢查字元串P是否是字元串T的子串。因為要檢查整個定長的字元串P，是以有時候這些算法稱為精确字元串比對算法。
為了便于讨論，假設給定的字元串T長度為n，要比對的字元串P的長度為m
           

/**
 * 方法一：蠻力法
 * 思路：
 * 檢查text中每一個可能位置，檢查pattern是否比對。由于text的長度為n，是以有n-m+1個可選的位置來比較。
 * 因為pattern的長度為m，是以TXT中最後的m-1個位置無需檢查。
 * @param text 文本
 * @param pattern 需要比對的字元串
 * @return 比對字元串在TXT中起始索引
 */
public static int bruteForceStringMatch(String text, String pattern) {
    // 擷取文本以及字元串的長度
    int n = text.length();
    int m = pattern.length();
    // 字元串轉換成字元數組
    char[] t = text.toCharArray();
    char[] p = pattern .toCharArray();
    // 精确比對
    // 隻檢查TXT的前n-m+1個可選的位置
    for (int i = ; i < (n - m + ); i++) {
        int j = ;
        while ((j < m) && (p[j] == t[j + i])) {
            j++;
        }
        // 如果比對則傳回TXT中比對的起始索引
        if (j == m) {
            return i;
        }
    }
    return -;
}
           

方法二：Robin-Karp算法

思路：

使用散列技術代替文本text中每個可能的位置進行檢查的方法，即僅在pattern的散列值和text中m個字元的散列值相等時才檢查具體字元是否相同。

舉例：

假設字元串的字元都是整數，即text中的所有字元都屬于{0,1,2,3,4,5,6,7,8,9}。由于所有字元都是整數，可以把m個連續的字元串看做十進制數。

例如字元串”61815”對應的十進制數是61815。

按照上面的假設，pattern可以看做一個十進制，假設pattern對應的十進制數為p

p = pattern[m-1] + 10*(pattern[m-2] + 10*(pattern[m-3] + … + 10*(pattern[1] + 10*pattern[0])…))

代碼實作，如下：

value = ;
for(int i = ; i < m; i++) {
    value = value * ;
    value = value + pattern[i];
}
           

text中m個字元對應的十進制為t(i)(i=0,1,2…n-m+1)

t(i+1) = 10 * (t(i) - 10^(m-1)*text[i+1]) + text(i+m+1)

例如，如果text=”123456”,m=3,t(0)=123,t(1)=10*(123-100*1)+4=234

逐漸解釋如下：

第一步：移除第一個數字，123-100*1=23

第二步：乘以10來移動第一步的結果，23*10=230

第三步：加上最後一個數字，230+4=234

然後算法對t(i)與p進行比較。當t(i)=p時，表示在text中找到子串pattern

參考：

http://www.ituring.com.cn/article/1759

http://www.geeksforgeeks.org/searching-for-patterns-set-3-rabin-karp-algorithm/

Robin-Karp算法代碼實作如下：

private static int d = ;             
private static int hashLength = ;    // hash表的長度，一般是個素數
public static int robinKarp(String text, String pattern) {
    // 擷取文本以及字元串的長度
    int n = text.length();
    int m = pattern.length();
    // 字元串轉換成字元數組
    char[] txt = text.toCharArray();
    char[] pat = pattern.toCharArray();

    // 擷取文本以及字元串的hash值
    int pHash = ;
    int tHash = ;
    // 計算pattern的hash值和text的前m個元素的hash值
    for (int i = ; i < m; i++) {
        pHash = (d * pHash + pat[i]) % hashLength;
        tHash = (d * tHash + txt[i]) % hashLength;
    }

    int h = ;
    // The value of h would be "pow(d, m-1) % hashLength"
    for (int i = ; i < m - ; i++) {
        h = (h * d) % hashLength;
    }

    // 精确比對
    // 隻檢查TXT的前n-m+1個可選的位置
    int j = ;
    for (int i = ; i <= (n - m); i++) {
        // 先檢查hash值是否相等
        if (pHash == tHash) {
            // hash值相等進而判斷字元是否相等
            for (j = ; j < m; j++) {
                if (pat[j] != txt[i + j]) {
                    break;
                }
            }
            // 如果比對則傳回text中比對的起始索引
            if (j == m) {
                return i;
            }
        }
        if (i < (n - m)) {
            tHash = (d * (tHash - txt[i] * h) + txt[i + m]) % hashLength;
            // We might get negative value of t, converting it to positive
            if (tHash < ) {
                tHash += hashLength;
            }
        }
    }
    return -;
}
           

方法三：KMP(Knuth Morris Pratt)字元串比對算法

詳細講解請參考：

http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

http://www.ituring.com.cn/article/59881

/**
 * 根據pattern構造部分比對表
 * @param pattern
 */
private static int[] F; // 字首函數、字首表或失配函數
public static void prefixTable(String pattern) {
    // 擷取文本以及字元串的長度
    int m = pattern.length();
    // 字元串轉換成字元數組
    char[] pat = pattern.toCharArray();

    // 初始化變量
    int i = ;
    int j = ;
    F = new int[m];
    F[] = ;

    while (i < m) {
        if (pat[i] == pat[j]) {
            F[i] = j + ;
            i++;
            j++;
        } else if (j > ) {
            j = F[j - ];
        } else {
            F[i] = ;
            i++;
        }
    }
}

public static int KMP(String text, String pattern) {
    // 擷取文本以及字元串的長度
    int n = text.length();
    int m = pattern.length();
    // 字元串轉換成字元數組
    char[] txt = text.toCharArray();
    char[] pat = pattern.toCharArray();

    // 構造部分比對表
    prefixTable(pattern);
    // 比對字元串
    int i = ;
    int j = ;
    while (i < n) {
        if (txt[i] == pat[j]) {
            if (j == (m - )) {
                return (i - j);
            } else {
                i++;
                j++;
            }
        } else if (j > ) {
            j = F[j - ];
        } else {
            i++;
        }
    }
    return -;
}