字串核对 java,c实现

《字串核对 java,c实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、FromGossip@caterpillarAlgorithmGossip:字串核對 說明今日的一些高階程式語言對於字串的處理支援越來越強大（例如Java、Perl等），不過字串搜尋本身仍是個值得探討的課題，在這邊以Boyer-Moore法來說明如何進行字串說明，這個方法快且原理簡潔易懂。解法字串搜尋本身不難，使用暴力法也可以求解，但如何快速搜尋字串就不簡單了，傳統的字串搜尋是從關鍵字與字串的開頭開始比對，例如Knuth-Morris-Pratt演算法字串搜尋，這個方法也不錯，不過要花時間在公式計算上；Boyer-Moore字串核對改由關鍵字的後面開始核對字串，並製作

2、前進表，如果比對不符合則依前進表中的值前進至下一個核對處，假設是p好了，然後比對字串中p-n+1至p的值是否與關鍵字相同。那麼前進表該如何前進，舉個實際的例子，如果要在字串中搜尋JUST這個字串，則可能遇到的幾個情況如下所示：依照這個例子，可以決定出我們的前進值表如下：其它JUST43214（match?）如果關鍵字中有重複出現的字元，則前進值就會有兩個以上的值，此時則取前進值較小的值，如此就不會跳過可能的位置，例如texture這個關鍵字，t的前進值應該取後面的3而不是取前面的7。實作·C#include#include#inc

3、ludevoidtable(char*);//建立前進表intsearch(int,char*,char*);//搜尋關鍵字voidsubstring(char*,char*,int,int);//取出子字串intskip[256];intmain(void){charstr_input[80];charstr_key[80];chartmp[80]={''};intm,n,p;printf("請輸入字串：");gets(str_input);printf("請輸入搜尋關鍵字：");gets(str_key);m=strlen(str_inpu

4、t);//計算字串長度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",tmp);p=search(p+n+1,str_input,str_key);}printf("");return0;}voidtable(char*key){intk,n;n=strlen(key);for(k=0;k<=255;k++)skip[k]=n;for(k=0;k

5、key[k]]=n-k-1;}intsearch(intp,char*input,char*key){inti,m,n;chartmp[80]={''};m=strlen(input);n=strlen(key);while(p

6、e;i++,j++)tmp[j]=text[i];tmp[j]='';}·Javaimportjava.io.BufferedReader;importjava.io.IOException;importjava.io.InputStreamReader;publicclassStringMatch{privateint[]skip;privateintp;privateStringstr;privateStringkey;publicStringMatch(Stringkey){skip=newint[256];this.key=key;for(intk=0;k

7、<=255;k++)skip[k]=key.length();for(intk=0;k