當前位置:首頁 » 操作系統 » 模式匹配演算法c

模式匹配演算法c

發布時間: 2023-07-11 16:36:52

A. 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改進演算法的模式匹配過程示意

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

C. 5e優先匹配c是多少分

5e優先匹配c是一千三分左右。

5E平台的分數不穩定,所以5E上900分對應官方匹配的段位范圍較廣,大約對應白銀三到黃金一段位。無法達到ak水平。

Csgo5E平台分數與官方匹配段位對應演算法:

ak對應1350分、麥穗對應1500分、雙ak對應1650分、菊花對應1800分、小老鷹對應1950分、大老鷹對應2100分。

Csgo官方匹配段位一覽:

等級01 Silver I 白銀—級。

等級02 Silver II 白銀二級。

等級03 Silver III 白銀三級。

等級04 Silver IV 白銀四級。

等級05 Silver Elite 白銀精英。

等級06 Silver Elite Master 大師級白銀精英。

等級07 Gold Nova I 黃金新星—級。

等級08 Gold Nova II 黃金新星二級。

5e優先匹配段位機制:

優先匹配段位機制是對於天梯系統的一項全新嘗試,它能更直觀地提供不同競技水平的參考,更准確地劃分玩家真實的競技水平,讓優先天梯分數更具含金量。

優先段位是為優先匹配和優先單排設立的專屬段位系統與排位系統,共分為S+、S、A、B、C、D、E、R、N 九個大段位。

2020年新賽季天梯將分為優先匹配、優先單排和天梯匹配(含天梯單排)三大排位模式。這三大排位模式中的所有段位、天梯分等數據都相互獨立互不影響,這意味著一名玩家最多可以擁有兩種段位和三種排位分數。

在優先匹配段位系統下,一名玩家的個人數據可以是:優先匹配3100分(S+段位)、優先單排2500分(A段位)、普通匹配1500分。

D. 解析一哈c語言中的kmp演算法,bf演算法,kr演算法之間的聯系與區別,盡量淺顯易懂,謝謝!

三種演算法聯系:都是字元串匹配演算法。
區別:
「KMP演算法」:在匹配過程稱,若發生不匹配的情況,如果next[j]>=0,則目標串的指針i不變,將模式串的指針j移動到next[j]的位置繼續進行匹配;若next[j]=-1,則將i右移1位,並將j置0,繼續進行比較。
「BF演算法」是普通的模式匹配演算法,BF演算法的思想就是將目標串S的第一個字元與模式串P的第一個字元進行匹配,若相等,則繼續比較S的第二個字元和P的第二個字元;若不相等,則比較S的第二個字元和P的第一個字元,依次比較下去,直到得出最後的匹配結果。
「KR演算法」在每次比較時,用HASH演算法計算文本串和模式串的HASH映射,通過比較映射值的大小來比較字元串是否匹配。但是考慮到HASH沖突,所以在映射值相同的時候,還需要近一步比較字元串是否相同。但是在每次比較時,需要計算HASH值,所以選擇合適的HASH演算法很重要。
略知一二!

E. 《數據結構(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
------------------------------
*/

熱點內容
小蟻攝像機如何雲存儲 發布:2025-03-17 09:42:42 瀏覽:815
如何修改自己的名字和密碼 發布:2025-03-17 09:32:20 瀏覽:787
寶馬3系槍灰色輪轂是哪個配置 發布:2025-03-17 09:28:17 瀏覽:513
鴻蒙系統退回安卓系統怎麼備份 發布:2025-03-17 09:14:33 瀏覽:614
資料庫服務公司 發布:2025-03-17 08:56:43 瀏覽:495
我的世界伺服器載入不了區塊 發布:2025-03-17 08:56:39 瀏覽:817
如何給無線路由器設置密碼 發布:2025-03-17 08:51:40 瀏覽:886
SQL閥 發布:2025-03-17 08:45:23 瀏覽:162
ipadpro第一代什麼配置 發布:2025-03-17 08:44:38 瀏覽:198
linuxjava進程查看 發布:2025-03-17 08:29:19 瀏覽:969