字串核对 java,c实现.doc

From GossipcaterpillarAlgorithm Gossip: 字串核對說明今日的一些高階程式語言對於字串的處理支援越來越強大（例如Java、Perl等），不過字串搜尋本身仍是個值得探討的課題，在這邊以Boyer- Moore法來說明如何進行字串說明，這個方法快且原理簡潔易懂。解法字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡單了，傳統的字串搜尋是從關鍵字與字串的開頭開始比對，例如 Knuth-Morris-Pratt 演算法 字串搜尋，這個方法也不錯，不過要花時間在公式計算上；Boyer-Moore字串核對改由關鍵字的後面開始核對字串，並製作前進表，如果比對不符合則依前進表中的值前進至下一個核對處，假設是p好了，然後比對字串中p-n+1至p的值是否與關鍵字相同。 那麼前進表該如何前進，舉個實際的例子，如果要在字串中搜尋JUST這個字串，則可能遇到的幾個情況如下所示：依照這個例子，可以決定出我們的前進值表如下： 其它JUST43214（match?）如果關鍵字中有重複出現的字元，則前進值就會有兩個以上的值，此時則取前進值較小的值，如此就不會跳過可能的位置，例如texture這個關鍵字，t的前進值應該取後面的3而不是取前面的7。實作 C #include #include #include void table(char*); / 建立前進表 int search(int, char*, char*); / 搜尋關鍵字 void substring(char*, char*, int, int); / 取出子字串 int skip256; int main(void) char str_input80; char str_key80; char tmp80 = 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(%sn, 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+) skipk = n; for(k = 0; k n - 1; k+) skipkeyk = n - k - 1; int search(int p, char* input, char* key) int i, m, n; char tmp80 = 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 += skipinputp; return -1; void substring(char *text, char* tmp, int s, int e) int i, j; for(i = s, j = 0; i = e; i+, j+) tmpj = texti; tmpj = 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 int256; this.key = key; for(int k = 0; k = 255; k+) skipk = key.length(); for(int k = 0; k key.length() - 1; k+) skipkey.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 += skipinput.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.r