模式匹配演算法無效位移是什麼

『壹』 串模式匹配演算法（C語言）100分懸賞

第一個樸素演算法:
1.普通的串模式匹配演算法:
int index(char s[],char t[],int pos)
/*查找並返回模式串T在S中從POS開始的位置下標,若T不是S的子串.則返回-1.*/
{
int i,j,slen,tlen;
i=pos;j=0; //i,j分別指示主串和模式串的位置.
slen=strlen(s);tlen=strlen(t); //計算主串和模式串的長度.
while(i<slen && j<tlen)
{
if(s[i]==t[j]) {i++;j++;}
else {i=i-j+1;j=0;}
}
if(j>=tlen) return i-tlen;
return -1;
}

第二個KMP演算法.該演算法支持從主串的任意位置開始搜索.
2.KMP演算法:
//求模式串的next函數.
void get_next(char *p,int next[])
{
int i,j,slen;
slen=strlen(p);i=0;
next[0]=-1;j=-1;
while(i<slen)
{
if(j==-1||p[i]==p[j]) {++i;++j;next[i]=j;}
else j=next[j];
}
}

//KMP模式匹配演算法
int index_kmp(char *s,char *p,int pos,int next[])
/* 利用模式串P的NEXT函數,求P在主串S中從第POS個字元開始的位置*/
/*若匹配成功.則返回模式串在主串中的位置下標.否則返回-1 */
{
int i,j,slen,plen;
i=pos-1;j=-1;
slen=strlen(s);plen=strlen(p);
while(i<slen && j<plen)
{
if(j==-1||s[i]==p[j]) {++i;++j;}
else j=next[j];

『貳』 KMP模式匹配演算法是什麼

KMP模式匹配演算法是一種改進演算法，是由D.E.Knuth、J.H.Morris和v.R.Pratt提出來的，因此人們稱它為「克努特－莫里斯－普拉特操作」，簡稱KMP演算法。此演算法可以在O（n＋m）的時間數量級上完成串的模式匹配操作。其改進在於：每當一趟匹配過程出現字元不相等時，主串指針i不用回溯，而是利用已經得到的「部分匹配」結果，將模式串的指針j向右「滑動」盡可能遠的一段距離後，繼續進行比較。

1.KMP模式匹配演算法分析回顧圖4－5所示的匹配過程示例，在第三趟匹配中，當i＝7、j＝5字元比較不等時，又從i＝4、j＝1重新開始比較。然而，經仔細觀察發現，i＝4和j＝1、i＝5和j＝1以及i＝6和j＝1這三次比較都是不必進行的。因為從第三趟部分匹配的結果就可得出，主串中的第4、5和6個字元必然是b、c和a（即模式串第2、第2和第4個字元）。因為模式中的第一個字元是a，因此它無須再和這三個字元進行比較，而僅需將模式向右滑動2個字元的位置進行i＝7、j＝2時的字元比較即可。同理，在第一趟匹配中出現字元不等時，僅需將模式串向右移動兩個字元的位置繼續進行i＝2、j＝1時的字元比較。由此，在整個匹配過程中，i指針沒有回溯，如圖1所示。

圖1改進演算法的模式匹配過程示意

『叄』 串的模式匹配是什麼

串的模式匹配即子串定位，是一種重要的串的運算。設S是給定的主串，T是給定的子串，在主串S中查找等於子串T的串的過程稱為模式匹配，T稱為模式串。如果在S中找到T子串，則稱匹配成功，函數返回T在S中首次出現的存儲位置（或序號），否則匹配失敗，返回0。為了運算方便，假設串採用順序存儲結構，串的長度存放在0號單元，串值從1號單元開始存放，這樣字元序號與存儲位置一致。

『肆』 串的模式匹配演算法中的BRUTE FORCE演算法在最好情況下的時間復雜度為什麼是O(n+m)而不是O(m)其中m是模式...

理解你的意思,你覺得O(m)是第一次搜索就找到推出函數了對吧, 這時候你可以認為是O(m), 但是 當 文本中找不到模式串的時候,比如 bbbbb中找a ,是不需要掃描一下文本bbbbb, 復雜度就是O(n), 說成O(n+m) 沒有太大意義

『伍』 C語言數據結構串的模式匹配演算法問題

和while循環裡面的一樣，i指針退回原來的位置並指向下一位，應該是多少？i-j+2是吧！

這里不用指向下一位，直接return它的位置就行了，於是return i-j+1

i-j+1和i-t[0]相等！

『陸』 數據結構關於串的KMP演算法的理解高手請進

KMP 演算法是一種字元串的模式匹配演算法，參看嚴蔚敏數據結構一書，裡面講的很清楚。
基本的字元串匹配演算法是將被匹配的字元串S和模式串T 逐個字元進行比較。例如:S中有10個字元，T中有5個字元。S串初始的匹配位置為3.則從S中的第3個字元與T中的第一個字元匹配，若相同則S的第4個字元與T中的第2個字元匹配。直到匹配成功或者出現失配字元。當出現失配情況下，移動標識S中當前進行比較的字元指針，會退到第4個字元處。然後，重復這一過程。簡單說，基本的字元匹配演算法是通過移動被匹配的字元串S，進行比較字元的指針位置來完成字元匹配的。
而KMP演算法剛好相反，在整個匹配過程中S中當前比較字元的指針並不發生回退現象，當出現S中的字元與T中的字元失配的時候。通過改變T的當前比較字元位置的指針來確定當前S中的字元該與T中哪個字元進行比較。簡單說，通過模式字元串T的當前比較字元的指針的回退來完成字元匹配。
當理解了KMP演算法通過改變T的當前比較字元位置的指針來完成匹配時，接下來要理清的是模式字元串T中的字元指針在失配的情況下是如何移動的。
以嚴蔚敏數據結構一書中KMP為例，對於模式字元串T，KMP維護了一個對應於T中每個字元弱發生失配情況下，指針回退到哪一位置的數組。當被匹配串S與模式串T發生失配的情況下，T讀取數組中相應記錄的位置，講指針回退。如果回退後仍然失配則S的當前比較字元位置指針+1，T串指針回到第一個字元處。
由此可見獲取數組中存儲的數據是KMP演算法的關鍵，書中的公式看起來有點抽象。數組中的存儲指針的位置是根據，模式串T與自身的匹配過程獲取的。
實際上是說，模式串T的第一個字元，如果出現失配則不會回退；當前比較位置的字元向前N-1位的子串恰好與T中從第一個字元起止N-1個字元形成的子串相等，且N小於當前位置，滿足這些條件的N的最大值即為T當前位置指針回退的位置，然後迭代此過程，直到T本身匹配或回退到第一個字元位置仍不匹配，則當前位置的對應的回退位置指針指向T中的第一個字元所在位置。

講的還不是很清楚，主要是對比一下基本的字元匹配演算法和KMP的不同。一個是通過移動被匹配字元串比較字元的指針來實現匹配，一個是移動模式字元串的當前比較字元的位置指針來實現匹配。對於匹配串字元回退位置這個計算書中已經很清楚，根據演算法單步調試一次自然就理解了。

『柒』 數據結構 字元串 模式匹配問題 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]作為長度的時候，把它從字元變成數字就行了)。

『捌』 C++語言中提供有關串的類

第四章：串(包括習題與答案及要點)

本章介紹了串的邏輯結構，存儲結構及串上的基本運算，由於在高級語言中已經提供了較全善的串處理功能，因此本章的重點是掌握在串上實現的模式匹配演算法。同時這也是本章的難點。但是從全書來講，這屬於較簡單的一章內容。

--------------------------------------------------------------------------------

1.串及其運算(領會)(這些內容比較容易理解，不用死記)

串就是字元串，是一種特殊的線性表，它的每個結點僅由一個字元組成。

空串：是指長度為零的串，也就是串中不包含任何字元(結點)。

空白串：指串中包含一個或多個空格字元的串。不同與空串，它的結點就是一個空格字元。

在一個串中任意個連續字元組成的子序列稱為該串的子串，包含子串的串就稱為主串。子串在主串中的序號就是指子串在主串中首次出現的位置。如A="I love you" B="love",則B在A中的序號為3，注意空格也是字元。

空串是任意串的子串，任意串是他自身的子串?

串分為兩種：串常量和串變數。串常量在程序中不能改變，串變數則可以。

關於串的基本運算，基本上在C語言中已經學過，主要有

求串長strlen(char *s)、

串復制strcpy(char *to,char *from)、

串聯接strcat(char *to,char *from)、

串比較charcmp(char *s1,char *s2)

和字元定位strchr(char *s, char c)等

這些基本運算通過練習來掌握。

--------------------------------------------------------------------------------

2.串的存儲結構(簡單應用)

串是特殊的線性表(結點是字元)，所以串的存儲結構與線性表的存儲結構類似。

串的順序存儲結構簡稱為順序串，順序串又可按存儲分配的不同分為靜態存儲分配的順序串和動態存儲分配的順序串。

靜態的意思可簡單地理解為一個確定的存儲空間，它的長度是不可變的。如直接使用定長的字元數組來定義一個串。它的優點是涉及串長的操作速度快，因為它的最大長度是不變的。

動態存儲分配就是在定義串時不分配存儲空間，直到需要使用時按所需串的長度分配存儲單元給它，並且在運行中還可以根據需要變化串的長度，這就是動態分配。不過這樣的串仍是順序存儲的，也就是說指針指向串的首地址，後面的結點是連續存儲的。

串的鏈式存儲就是用單鏈表的方式存儲串值，串的這種鏈式存儲結構簡稱為鏈串。鏈串與單鏈表的差異只是它的結點數據域為單個字元。這種存儲結構方便於串的插入和刪除操作，但是空間利用率不高，因為存放每一個字元要"搭配"一個指向下一字元的地址,而地址所佔空間是比較大的。為了解決這種"存儲密度"過低的狀況，可以讓一個結點存儲多個字元，事實上這是順序串和鏈串的綜合(折衷)。

--------------------------------------------------------------------------------

本章的重點和難點就是串運算的實現，特別是順序串上子串定位的運算。

子串定位運算又稱串的"模式匹配"或"串匹配"，就是在主串中查找出子串出現的位置，這在應用中非常廣泛，比如文本編輯中的"查找和替換"用到的就是子串定位運算的演算法。

在串匹配中，將主串稱為目標(串)，子串稱為模式(串)，我們這樣想像，子串就如同一個模板(樣本)，用它在目標上對比，從頭往後比較，凡是遇到一模一樣的那麼一段，就算找到一個位置了(我們就說，從這個位置開始的匹配成功)。用很專業的很酷的話說就是"模式在目標中出現"(我想起了警匪片里的對話),如果這個模板對應的目標串中有不一樣的字元出現，那麼這個位置就匹配失敗。

當我們用這個模子依次從目標的頭部往後移,移動到的位置就叫位移，如果每次向右移動1格，那麼每次的位移就加上1。

每次移動後要看看模板里的字元和目標中相應的字元是否相等，如果都相同，這次位移就叫有效位移(其實就是從這個位置開始的匹配成功)

另外有一個合法位移和不合法位移的概念，就是說，移動一個位置後，如果模板的最後一個字元還沒有超出目標串中最後一個字元時，這個位移就是合法位移，如果超出了，那麼就沒有比較的意義了，這時就是不合法位移。

這是比較容易理解的，串匹配問題就是找出給定模式串P在給定目標串T中首次出現的有效位移或者是全部有效位移。

具體的串匹配演算法也不是很難理解，就是用兩個循環，外循環用於進行模式的位移，內循環進行模板內每個字元的比較(判斷是否有效位移)。關於串匹配的時間復雜度，在最壞的情況下就是目標串和模式串分別是"a^n-1b"和"a^m-1b"的形式，就是說，每一次合法位移後，在內循環中都要比較m個字元才知道是不是有效位移(前面的字元都是一樣的)。所以最壞的情況下時間復雜度是O((n-m+1)m),假如m與n同階的話則它是O(n^2)。

鏈串上的子串定位運算的不同之處就是位移是結點地址而不是整數。理解一下演算法即可。

真正的應用主要還是要掌握串的基本演算法並用它們構造出可以解決具體問題的簡單演算法。

第四章 串 復習要點

本章復習要點是：

串是一種特殊的線性表，它的結點僅由一個字元組成。

空串與空白串的區別：空串是長度為零的串，空白串是指由一個或多個空格組成的串。

串運算的實現中子串定位運算又稱串的模式匹配或串匹配。

串匹配中，一般將主串稱為目標(串),子串稱為模式(串)。

本章可能出的題型多半為選擇、填空等。

『玖』 Java編程實現字元串的模式匹配

傳統的字元串模式匹配演算法（也就是BF演算法）就是對於主串和模式串雙雙自左向右，一個一個字元比較，如果不匹配，主串和模式串的位置指針都要回溯。這樣的演算法時間復雜度為O（n＊m），其中n和m分別為串s和串t的長度。

KMP 演算法是由Knuth，Morris和Pratt等人共同提出的，所以成為Knuth－Morris－Pratt演算法，簡稱KMP演算法。KMP演算法是字元串模式匹配中的經典演算法。和BF演算法相比，KMP演算法的不同點是匹配過程中，主串的位置指針不會回溯，這樣的結果使得演算法時間復雜度只為O（n＋m）。

『拾』 數據結構（c++）字元串 模式匹配演算法問題，對高手來說只要寫一點點

#include <string>
using namespace std;

string s = "zabcdefg";

int index1(const string ss, int pos)
{
if (pos<0 || pos>s.length())
printf("pos²»ºÏ·¨£¡");
int i = pos, j = 0;

while (i < s.length() && j < ss.length()) {
if (s[i]==ss[j]) {
i++;
j++;
} else {
i=i-j+1;
j=0;
}
}

if (j>=ss.length())
return (i-j+1);
else
return -1;
}
void getnext(const string ss, int *next)
{
int i = 0, j = -1;
next[i] = -1;
while (i < ss.length()) {
if (j == -1 || s[i] == ss[j]) {
i++;
j++;
next[i]=j;
} else
j = next[j];
}
}

int index2(const string ss, int pos)
{
int *next = new int[ss.length()];
getnext(ss, next);

int i = pos, j = 0;
while (i < s.length() && j < ss.length()) {
if (j==0 || s[i]==ss[j] ) {
++i;
++j;
} else {
j = next[j];
}
}

if (j >= ss.length())
return i-ss.length()+1;
else
return -1;
}

int main()
{
string ss = "abc";
printf("index1: %d, index2: %d\n", index1(ss, 0), index2(ss, 0));

return 0;
}