近似模式串匹配演算法

A. 串的模式匹配是什麼

就是拿T串從S串(稱為主串)去尋找在S串是否存在這么一個T串,如果存在，則說明T串是S串的子串並返回首次查找成功的位置(也稱為索引)。

它的演算法原理是比較簡單的，就是拿T串從S串的首位置(通常用一個變數來記住它的位置稱為S串的指針)開始逐一匹配，如發生失配時則從S串的第二個位置開始重新匹配,依此類型，直到完全匹配為止,或指向S串的指針已到達末尾。 這種演算法也稱為樸素演算法。效率是最低的。相應地效率高的是
由D.E.Knuth 美國計算機科學家人稱演算法之父高德納和另兩位科學家V.R.Pratt和J.H.Morris發明的KMP演算法

B. C語言數據結構串的模式匹配演算法問題

和while循環裡面的一樣，i指針退回原來的位置並指向下一位，應該是多少？i-j+2是吧！
這里不用指向下一位，直接return它的位置就行了，於是return
i-j+1
i-j+1和i-t[0]相等！

C. 實現串的簡單模式匹配演算法。要求：輸入主串S和子串T，若在主串S中存在和T相等的子串，則返回在S中出現的

首先你得把主串和字串獲取成兩個字元數組，這部分我就不給你寫了，假定我們已經有了兩個數組s[]和t[]一下為匹配部分的演算法：
int i,j,k;
for(i=0;i<t.lenth;t++ )
{
if(s[i]=t[0])
{
for(j=0;j<t.length;j++)
{
if(s[i+j]=t[j])
{
continue;
}
else
{
break;
}
}
if(j=(t.length-1))
{return i;}
continue;
}
continue;
}
return 0;

D. Java編程實現字元串的模式匹配

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

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

E. 字元串匹配的匹配種類

柔性字元串匹配
1974年Fischer和Paterson將通配符don't cares引入模式匹配問題 ，之後模式匹配的定義出現了各種各樣非標准形式：按匹配方式分，有容錯的近似匹配，交換相鄰字母的交換匹配，服務於程序代碼查錯的參數匹配等；按匹配對象分，T、P可以是一張二維表，也可以分別含有通配符；按匹配結果分，有返回匹配位置和匹配數兩種定義。Muthukrishna等人將上述各類問題統稱為Non-standard Stringology 。然而，通配符的引入會讓問題定義更加靈活，卻也帶來了復雜性。演算法的設計有時不僅僅考慮時空效率，保證匹配結果的完備性很可能成為演算法設計更重要的問題。甚至其中的某些問題被猜測具有NP難度。
帶有通配符的串匹配
在Fischer和Paterson於1974年將通配符*引入模式匹配問題之後，如何將通配符與傳統的模式匹配有效結合是研究的重點。這其中，最具代表性的定義是通配符指代的字元數不僅僅用一個固定的常數表示，而是一個可由用戶自定義的區間 ，即帶有上下限約束，如TCT*(30,50)TATA。 將上述帶有區間的通配符擴展至任意兩兩相鄰的字元之間，然而所有的通配符上下限相同，如A*(1,3)C*(1,3)G*(1,3)C。為了進一步放寬約束， 提出了不同通配符彼此獨立的思想，如A*(0,3)C*(2,4)G*(1,1)C。 序列模式挖掘是數據挖掘的一個重要分支，是基於時間或者其他序列的經常發生的模式。序列模式的一個例子就是「一個9個月前買了一台PC的顧客有可能在一個月內買一個新的CPU」。很多數據都是這種時間序列形式的，我們就可以用它來市場趨勢分析，客戶保留和天氣預測等等。序列模式首先是由R.Agrawal和R.Srikant提出的，隨後幾年研究者所提出的演算法都是基於Apriori原理的改進演算法。隨後Zaki等人提出了基於垂直數據表示的SPADE演算法。Han等提出了不產生候選集的基於模式增長的FP-Growth演算法。接著Han等又研究出了基於投影資料庫的FreeSpan和PrefixSpan演算法。

F. 《數據結構（C語言版）》之「串的模式匹配演算法」

# include <string.h>
# include <stdio.h>
# include <stdlib.h>
# define OK 1
# define ERROR 0
typedef int Status;
//串的定長順序存儲結構
# define MAX_STR_LEN 40
typedef char SString[MAX_STR_LEN + 1];//0號單元存放串的長度
Status StrAssign(SString T,char * chars)//生成一個其值等於chars的串T
{
int i;
if (strlen(chars) > MAX_STR_LEN)
{
return ERROR;
}
else
{
T[0] = strlen(chars);
for (i=1; i<=T[0]; ++i)
{
T[i] = * (chars + i - 1);
}
return OK;
}
}
//返回串S的元素的個數
int StrLength(SString S)
{
return S[0];
}
//用Sub返回串S的自第pos個字元起長度為len的子串
Status SubString(SString Sub,SString S,int pos,int len)
{
int i;
if (pos<1 || pos>S[0] || len<0 || len>S[0]-pos+1)
{
return ERROR;
}
for (i=1; i<=len; ++i)
{
Sub[i] = S[pos+i-1];
}
Sub[0] = len;
return OK;
}
//輸出字元串T
void StrPrint(SString T)
{
int i;
for (i=1; i<=T[0]; ++i)
{
printf("%c ",T[i]);
}
printf("\n");
}
//求模式串T的next函數值並存入數組next
void get_next(SString T,int next[])
{
int i = 1,j = 0;
next[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
next[i] = j;
}
else
{
j = next[j];
}
}
}
//求模式串T的next函數修正值並存入數組nextval
void get_nextval(SString T,int nextval[])
{
int i = 1,j = 0;
nextval[1] = 0;
while (i < T[0])
{
if (j==0 || T[i]==T[j])
{
++i;
++j;
if (T[i] != T[j])
{
nextval[i] = j;
}
else
{
nextval[i] = nextval[j];
}
}
else
{
j = nextval[j];
}
}
}
//利用模式串T的next函數求T在主串S中第pos字元之後的位置的KMP演算法
//1=<pos=<StrLength(S)
int Index_KMP(SString S,SString T,int pos,int next[])
{
int i = pos,j = 1;
while (i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j])
{
++i;
++j;
}
else
{
j = next[j];
}
}
if (j > T[0])
{
return i - T[0];
}
else
{
return 0;
}
}
int main(void)
{
int i,* p;
SString s1,s2;
StrAssign(s1,"aaabaaaab");
printf("主串為：");
StrPrint(s1);
StrAssign(s2,"aaaab");
printf("子串為：");
StrPrint(s2);
p = (int *)malloc((StrLength(s2) + 1) * sizeof(int));
get_next(s2,p);
printf("子串的next的數組為：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
i = Index_KMP(s1,s2,1,p);
if (i)
{
printf("主串和子串在第%d個字元處首次匹配\n",i);
}
else
{
printf("主串和子串匹配不成功\n");
}
get_nextval(s2,p);
printf("子串的nextval數組為：");
for (i=1; i<=StrLength(s2); ++i)
{
printf("%d ",* (p+i));
}
printf("\n");
printf("主串和子串在第%d個字元處首次匹配\n",Index_KMP(s1,s2,1,p));
printf("求串s1的從第5個字元起長度為5的子串s2:\n");
SubString(s2,s1,5,5);
printf("串s2為:");
StrPrint(s2);
return 0;
}
/*
在vc++6.0中的輸出結果：
------------------------
主串為：a a a b a a a a b
子串為：a a a a b
子串的next的數組為：0 1 2 3 4
主串和子串在第5個字元處首次匹配
子串的nextval數組為：0 0 0 0 4
主串和子串在第5個字元處首次匹配
求串s1的從第5個字元起長度為5的子串s2:
串s2為:a a a a b
Press any key to continue
------------------------------
*/

G. 數據結構串匹配十大經典演算法

1。
int Index(SString S,SString T,int pos)
{
//返回子串T在主串S中第pos個字元之後的位置。若不存在，則函數值為0。
//其中，T非空，1〈=pos<=Stringlength(S).
i=pos;j=1;
while(i<=S[0] && j<=T[0])
{
if (S[i]== T[i]) {++i;++j;}
else { i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}//Index
2。

int Index-KMP(SString S,SString T,int pos)
{
//利用模式串T的next函數值求T在主串S中第pos 個字元之後的位置的KMP演算法。其中，T非空，1<=pos<=Stringlength(S)
i=pos;
j=1;
while(i<=S[0] && j<=T[0])
{
if (j==0 || S[i]==T[j]) {++i; ++j;}
else j=next[j];
}
if (j>T[0]) return i-T[0];
else return 0;
//Index}
下面是next函數：
void next(SString S,ing next[])
{
i=1;
next[1]=0;
j=0;
while (i<T[0])
{
if (j==0 || T[i]==T[j]){ ++i; ++j;
next[j]=i;}
else j=next[j];
}
}//next

我現在只有這兩個答案。

H. 數據結構（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;
}

I. 串模式匹配演算法（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];

J. 串的模式匹配

基本思想：從主串s的第pos個字元起和模式的地一個字元比較，若等，則繼續，否則從主串的下個字元起再重新和模式字元比較，直到全部符合。
基本演算法：int Index(SSteing T,int pos)
{i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{if(S[i]++T[j]){++i;++j;}
else{i=i-j+2;j=1;}
}
if(j>T[0])return i-T[0];
else return 0;
}