字元串匹配演算法
只需要實例化 類Matching 設置參數 並調用m.getIndex()方法就OK 請測試... public class Test18{
public static void main(String[] args){
Matching m = new Matching();
m.setOrgStr("ALSKLSHFKDLLS");
m.setSubStr("LS");
System.out.println(m.getIndex());
}
}
class Matching{
String orgStr ="";
String subStr ="";
public void setOrgStr(String orgStr){
this.orgStr = orgStr;
}
public void setSubStr(String subStr){
this.subStr = subStr;
}
public String getIndex(){
StringBuffer sb = new StringBuffer("{");
//根據關鍵字subStr來拆分字元串orgStr所得的字元串數組
String[] sub = orgStr.split(subStr);
int keyLength = subStr.length(); //關鍵字長度
int keySize = 0; //關鍵字個數
int subSize = sub.length; //子字元串個數
int subLength = 0; //子字元串長度
if(!orgStr.endsWith(subStr)){
keySize = subSize-1;
}else
keySize = subSize; int[] index = new int[keySize];//關鍵字下標數組
for(int i=0;i<keySize;i++){
subLength = sub[i].length();
if(i==0){
index[i]=subLength;
}else
index[i]=index[i-1]+subLength+keyLength;
}
if(keySize>0){
int l = keySize-1;
for(int i=0;i<l;i++){
sb.append(index[i]+",");
}
sb.append(index[l]);//最後一個關鍵字下標
}else{
sb.append("NULL");
}
sb.append("}");
return sb.toString();
}
}
⑵ 字元串匹配演算法，最快的是哪種
目前在我遇到的字元串匹配演算法中，最快的應該是sunday演算法了。。
(BF、KMP、BM、sunday)
⑶ 想找一個解決兩個字元串匹配程度的演算法。
假設string1="abcde",string2="bcd",則分析邏輯如下：
1. 如果string2長於string1，則不匹配
2. 在string1中順序查匹配string2中第一個字元的字元，
查到後，如果string1餘下的字元串長度小於string2的長度，則不匹配
3. 在上述條件滿足時，將string1的下一個字元和string2中的第二個字元匹配，以此類推，一旦有一個不匹配，則不匹配。回到第2步，查找下一個和string2首字元一致的字元。
4. 如果string2中的字元全都匹配上，則說明string2中string1中識別出來了。
⑷ 題目：KMP演算法的實現 內容： 實現字元串匹配的簡單匹配演算法和KMP演算法，並且使用相同的比較字元串重復比較
shit
⑸ 關於一個字元串匹配演算法
我看了一下代碼的，大概覺得它主要實現的功能是查找*y對應字元串中是否有與*x對應的字元串相等的子字元串存在，如果存在則返回該子串第一個字元在*y中的位置。
但是你沒有把問題說清楚，比如preBmBc和memcmp這兩個函數是在你給的程序中沒有定義的，我猜了好久都不能猜出他們確切的用途。我估計你們老師主要也是叫你們實現這兩個函數吧。。
如果你能在把問題給得詳細的。。我可以繼續幫你想想。。
不愧是畢業設計的題目啊，確實有點難度啊。我覺得那個函數不是一個簡單的字元串匹配演算法，它是一個多重字元串匹配演算法。我給你個C語言的例子你參考一下吧。一下兩下我也搞不出來了，真不好意思。
boyermoore演算法的sample程序
TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind)
{
//
// 聲明：
// 該段代碼只是BoyerMoore(名字也許不準確)的基本思想，當
// 然不是最優的，具體完善工作就留給你自己樂！嘻嘻。
// 該演算法的本質就是從字元串的右端而不是左端開始比較，這
// 樣，當查詢不匹配時才有可能直接躍過多個字元（最多可以躍過
// strlen(sFind)個字元），如果最右邊的字元匹配則回溯。比如：
//
// pain
// ^ 這是第一次比較n和空格比
// The rain in SpainThe rain in Spain
//
// pain
// ^ 這是第二次比較，好爽呀！
// The rain in SpainThe rain in Spain
//
// 當然，這樣比較會產生一些問題，比如：
//
// pain
// ^ （圖1）
// The rain in SpainThe rain in Spain
//
// 如果比較到這兒，大家都會看到，只需再向後移到兩個字元
// 就匹配成功了，但如果接下去還按上面的方法跳strlen(sFind)的
// 話，就會錯過一次匹配！！！！！
//
// pain
// ^
// The rain in SpainThe rain in Spain
//
// 怎麼辦？當然可以解決！大家回頭看圖1，當時a是pain的子
// 串，說明有可能在不移動strlen(sFind)的跨度就匹配成功，那就
// 人為地給它匹配成功的機會嘛！串一下pain串，直接讓兩個a對齊
// 再做比較！呵呵，如果要比較的字元不是pain的子串，當然就可
// 以直接跨過strlen(sFind)個字元了！不知我說明白沒？
//
//
// 查詢串的長度
int nLenOfFind = lstrlen(sFind);
// 被查詢串的長度
int nLenOfSrc = lstrlen(sSrc);
// 指向查詢串最後一個字元的指針
TCHAR * pEndOfFind = sFind + nLenOfFind -1;
// 指向被查詢串最後一個字元的指針
TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1;
// 在比較過程中要用到的兩個指針
TCHAR * pSrc = sSrc;
TCHAR * pFind;
// 總不能一直讓它比較到win.com文件的地址去吧？嘻嘻！
while ( pSrc <= pEndOfSrc ) {
// 每次匹配都是從右向左，這是本演算法的核心。
pFind = pEndOfFind;
// 如果比較不成功，被查詢串指針將向右串的字元數
int nMoveRightSrc;
// 比較被查詢串的當前字元是否和查詢串的最右邊字
// 符匹配，如果匹配則回溯比較，如果全匹配了，該
// 干什麼，我就不用說了吧？:-)
while ( pFind >= sFind ) {
// TNND，白廢功夫比了！看看需要向右移動幾個
// 字元吧（如果說從右到左是本演算法的核心，則
// 判斷向右移幾個字元則是本演算法的技巧）。
if ( *pSrc != *pFind ) {
// 被查詢串的當前字元是否在查詢串里？
TCHAR * p = strrchr( sFind, *pSrc );
// 沒在，直接移lstrlen(sFind)個字元
if ( NULL == p )
nMoveRightSrc = nLenOfFind;
else
// 哇塞！真的在，那就只需...
nMoveRightSrc = pEndOfFind - p;
break;
}
// 哈！又匹配成功了一個！接著向左回溯...
pFind --;
pSrc --;
}
// 如果在上面的while循環里每一次比較都匹配了
// 那就對了唄！告訴用戶找到了
if ( pFind < sFind )
return ( pSrc + 1 );
// 沒匹配成功，nMoveRightSrc上面已經算好了
// 直接用就可以了。
pSrc += nMoveRightSrc;
}
// 程序運行到這兒肯定是沒指望了！
return NULL;
}
行了，函數寫完了，我們可以試一下了！
void CTNNDDlg::OnButton1()
{
TCHAR sSrc[] = "The rain in Spain";
TCHAR sFind[]= "pain";
TCHAR * pFound = BoyerMooreSearch( sSrc, sFind );
if ( pFound )
MessageBox(pFound);
else
MessageBox("沒找到");
}
//另外一個
void preBmBc(char *x, int m, int bmBc[]) {
int i;
for (i = 0; i < ASIZE; ++i)
bmBc[i] = m;
for (i = 0; i < m - 1; ++i)
bmBc[x[i]] = m - i - 1;
}
void suffixes(char *x, int m, int *suff) {
int f, g, i;
suff[m - 1] = m;
g = m - 1;
for (i = m - 2; i >= 0; --i) {
if (i > g && suff[i + m - 1 - f] < i - g)
suff[i] = suff[i + m - 1 - f];
else {
if (i < g)
g = i;
f = i;
while (g >= 0 && x[g] == x[g + m - 1 - f])
--g;
suff[i] = f - g;
}
}
}
void preBmGs(char *x, int m, int bmGs[]) {
int i, j, suff[XSIZE];
suffixes(x, m, suff);
for (i = 0; i < m; ++i)
bmGs[i] = m;
j = 0;
for (i = m - 1; i >= -1; --i)
if (i == -1 || suff[i] == i + 1)
for (; j < m - 1 - i; ++j)
if (bmGs[j] == m)
bmGs[j] = m - 1 - i;
for (i = 0; i <= m - 2; ++i)
bmGs[m - 1 - suff[i]] = m - 1 - i;
}
void BM(char *x, int m, char *y, int n) {
int i, j, bmGs[XSIZE], bmBc[ASIZE];
/* Preprocessing */
preBmGs(x, m, bmGs);
preBmBc(x, m, bmBc);
/* Searching */
j = 0;
while (j <= n - m) {
for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i);
if (i < 0) {
OUTPUT(j);
j += bmGs[0];
}
else
j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i);
}
}
⑹ 數據結構 字元串 模式匹配問題 KMP演算法
你的程序本身思路沒有錯，但錯在以下幾點：
1.在程序中有字元串S和T，你用S[0]代表字元串的長度，但S是字元串，S[0]是長度嗎？
2.在main函數中，你輸入的S和T都是用gets(S)或gets(T),那麼它們都是以下標0開頭的，你應該要進行處理，使它以下標1作為開頭（可以這樣gets(&S[1]); 然後S[0] = strlen(&S[1]) + '0';在用S[0]作為長度的時候，把它從字元變成數字就行了)。
⑺ 字元串匹配演算法是怎麼算的
這是一個畢業老師出的字元串的演算法的題目！這是答案 可以參考一下！ boyermoore演算法的sample程序 TCHAR * BoyerMooreSearch(TCHAR *sSrc, TCHAR *sFind) { // // 聲明： // 該段代碼只是BoyerMoore(名字也許不準確) 的基本思想，當 // 然不是最優的，具體完善工作就留給你自己樂！嘻嘻。 // 該演算法的本質就是從字元串的右端而不是左端開始比較，這 // 樣，當查詢不匹配時才有可能直接躍過多個字元（最多可以躍過 // strlen(sFind)個字元）， 如果最右邊的字元匹配則回溯。比如： // // pain // ^ 這是第一次比較n和空格比 // The rain in SpainThe rain in Spain // // pain // ^ 這是第二次比較，好爽呀！ // The rain in SpainThe rain in Spain // // 當然，這樣比較會產生一些問題，比如： // // pain // ^ （圖1） // The rain in SpainThe rain in Spain // // 如果比較到這兒，大家都會看到，只需再向後移到兩個字元 // 就匹配成功了，但如果接下去還按上面的方法跳strlen( sFind)的 // 話，就會錯過一次匹配！！！！！ // // pain // ^ // The rain in SpainThe rain in Spain // // 怎麼辦？當然可以解決！大家回頭看圖1，當時a是pain的子 // 串，說明有可能在不移動strlen(sFind) 的跨度就匹配成功，那就 // 人為地給它匹配成功的機會嘛！串一下pain串， 直接讓兩個a對齊 // 再做比較！呵呵，如果要比較的字元不是pain的子串，當然就可 // 以直接跨過strlen(sFind)個字元了！ 不知我說明白沒？ // // // 查詢串的長度 int nLenOfFind = lstrlen(sFind); // 被查詢串的長度 int nLenOfSrc = lstrlen(sSrc); // 指向查詢串最後一個字元的指針 TCHAR * pEndOfFind = sFind + nLenOfFind -1; // 指向被查詢串最後一個字元的指針 TCHAR * pEndOfSrc = sSrc + nLenOfSrc -1; // 在比較過程中要用到的兩個指針 TCHAR * pSrc = sSrc; TCHAR * pFind; // 總不能一直讓它比較到 win.com 文件的地址去吧？嘻嘻！ while ( pSrc <= pEndOfSrc ) { // 每次匹配都是從右向左，這是本演算法的核心。 pFind = pEndOfFind; // 如果比較不成功，被查詢串指針將向右串的字元數 int nMoveRightSrc; // 比較被查詢串的當前字元是否和查詢串的最右邊字 // 符匹配，如果匹配則回溯比較，如果全匹配了，該 // 干什麼，我就不用說了吧？:-) while ( pFind >= sFind ) { // TNND，白廢功夫比了！看看需要向右移動幾個 // 字元吧（如果說從右到左是本演算法的核心，則 // 判斷向右移幾個字元則是本演算法的技巧）。 if ( *pSrc != *pFind ) { // 被查詢串的當前字元是否在查詢串里？ TCHAR * p = strrchr( sFind, *pSrc ); // 沒在，直接移lstrlen(sFind)個字元 if ( NULL == p ) nMoveRightSrc = nLenOfFind; else // 哇塞！真的在，那就只需... nMoveRightSrc = pEndOfFind - p; break; } // 哈！又匹配成功了一個！接著向左回溯... pFind --; pSrc --; } // 如果在上面的while循環里每一次比較都匹配了 // 那就對了唄！告訴用戶找到了 if ( pFind < sFind ) return ( pSrc + 1 ); // 沒匹配成功，nMoveRightSrc上面已經算好了 // 直接用就可以了。 pSrc += nMoveRightSrc; } // 程序運行到這兒肯定是沒指望了！ return NULL; } 行了，函數寫完了，我們可以試一下了！ void CTNNDDlg::OnButton1() { TCHAR sSrc[] = "The rain in Spain"; TCHAR sFind[]= "pain"; TCHAR * pFound = BoyerMooreSearch( sSrc, sFind ); if ( pFound ) MessageBox(pFound); else MessageBox("沒找到"); } //另外一個 void preBmBc(char *x, int m, int bmBc[]) { int i; for (i = 0; i < ASIZE; ++i) bmBc[i] = m; for (i = 0; i < m - 1; ++i) bmBc[x[i]] = m - i - 1; } void suffixes(char *x, int m, int *suff) { int f, g, i; suff[m - 1] = m; g = m - 1; for (i = m - 2; i >= 0; --i) { if (i > g && suff[i + m - 1 - f] < i - g) suff[i] = suff[i + m - 1 - f]; else { if (i < g) g = i; f = i; while (g >= 0 && x[g] == x[g + m - 1 - f]) --g; suff[i] = f - g; } } } void preBmGs(char *x, int m, int bmGs[]) { int i, j, suff[XSIZE]; suffixes(x, m, suff); for (i = 0; i < m; ++i) bmGs[i] = m; j = 0; for (i = m - 1; i >= -1; --i) if (i == -1 || suff[i] == i + 1) for (; j < m - 1 - i; ++j) if (bmGs[j] == m) bmGs[j] = m - 1 - i; for (i = 0; i <= m - 2; ++i) bmGs[m - 1 - suff[i]] = m - 1 - i; } void BM(char *x, int m, char *y, int n) { int i, j, bmGs[XSIZE], bmBc[ASIZE]; /* Preprocessing */ preBmGs(x, m, bmGs); preBmBc(x, m, bmBc); /* Searching */ j = 0; while (j <= n - m) { for (i = m - 1; i >= 0 && x[i] == y[i + j]; --i); if (i < 0) { OUTPUT(j); j += bmGs[0]; } else j += MAX(bmGs[i], bmBc[y[i + j]] - m + 1 + i); } }
⑻ 字元串匹配演算法的基本思想是什麼
這個用到了正規表達式對字元串的匹配.程序如下,是javascript的.
<script language="javascript">
function check(obj)
{var str=/^[0-9]{4}-[0-9]{7}$/ig;
if(str.test(obj))
alert("this is your number");
else
alert("write again");}
</script>
<form name="form1">
<input type="text" name="mytext" size="12">
<input type="button" value="click" onclick="check
(form1.mytext.value)">
</form>
要求輸入的是標准電話號碼.看不懂問我.呵呵.
⑼ 字元串匹配的傳統演算法
傳統的匹配演算法
串匹配演算法雖然發展了幾十年，然而非常實用的演算法是近年才出現。串匹配問題的研究存在理論研究和實際應用的脫節。那些專門從事演算法研究的學者關心的只是理論上看起來很美妙的演算法——具有很好的時間復雜度。而開發人員只追求實際應用中盡可能快的演算法。兩者之間從不注意對方在干什麼。將理論研究和實際應用結合的演算法(如BNDM演算法)只是近年才出現。在實際應用中常常很難找到適合需求的演算法——這樣的演算法實際上是存在的，但是只有資深專家才比較了解。考慮如下情況，一位軟體開發人員，或者一位計算生物學家，或者一位研究人員，又或者一位學生，對字元串匹配領域並沒有深入了解，可是現在需要處理一個文本搜索問題。那些汗牛充棟的書籍使得閱讀者淹沒在各種匹配演算法的海洋中，卻沒有足夠的知識選擇最適用的演算法。最後，常常導致這樣的局面：選擇一種最簡單的演算法加以實現。這往往導致很差的性能，從而影響整個開發系統的質量。更糟糕的是，選擇了一個理論上看起來很漂亮的演算法，並且花費了大量精力去實現。結果，卻發現實際效果和一個簡單演算法差不多，甚至還不如簡單演算法。因此，應該選用一種「實用」演算法，即在實際應用中性能較好，並且一個普通程序員能在幾小時內完成演算法的實現代碼。另外，在字元串匹配研究領域中，一個人所共知的事實是「演算法的思想越簡單，實際應用的效果越好」。
傳統的串匹配演算法可以概括為前綴搜索、後綴搜索、子串搜索。代表演算法有KMP，Shift-And，Shift-Or，BM，Horspool，BNDM，BOM等。所用到的技術包括滑動窗口、位並行、自動機、後綴樹等。
