c字元串匹配演算法

❶ Linux c語言 在文件中查找字元串匹配關鍵字

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define FILE_NAME_MAX 50
#define SEPERATE_STRING_MAX 100

int StrCount(FILE *file,char *str);

int main()
{
char *filename,*spestr;
FILE *fp;
filename=(char *)malloc(FILE_NAME_MAX);
spestr=(char *)malloc(SEPERATE_STRING_MAX);
printf("Input the filename:");
while(1)
{
scanf("%s",filename);
fp=fopen(filename,"r");
if(fp!=NULL)
{
break;
}
printf("Can't open the file.Try Again!");
}
printf("Input the special string:");
scanf("%s",spestr);

printf("%d times of %s in %s.",StrCount(fp,spestr),spestr,filename);

fclose(fp);
free(filename);
free(filename);

return 0;
}

int StrCount(FILE *file,char *str)
{
int count=0;
char ch;
int p=0;;

while((ch=fgetc(file))!=EOF)
{
// 當前讀入的字元匹配 str 相應位置的字元
if(ch == str[p])
{
// 匹配下一個字元
p++;
// 如果已經匹配成功
if(str[p] == '\0')
{
count++;
// 從頭開始重新匹配
p = 0;
}
}
// // 當前讀入的字元不匹配 str 相應位置的字元
else
{

❷ 求字元串匹配BM演算法的代碼，要c或者c++的。

BM演算法的C語言實現：

// 函數：int* MakeSkip(char *, int)
// 目的：根據壞字元規則做預處理，建立一張壞字元表
// 參數：
// ptrn => 模式串P
// PLen => 模式串P長度
// 返回：
// int* - 壞字元表
int* MakeSkip(char *ptrn, int pLen)
{
int i;
//為建立壞字元表，申請256個int的空間
//PS:之所以要申請256個，是因為一個字元是8位，
// 所以字元可能有2的8次方即256種不同情況
int *skip = (int*)malloc(256*sizeof(int));

if(skip == NULL)
{
fprintf(stderr, "malloc failed!");
return 0;
}

//初始化壞字元表，256個單元全部初始化為pLen
for(i = 0; i < 256; i++)
{
*(skip+i) = pLen;
}

//給表中需要賦值的單元賦值，不在模式串中出現的字元就不用再賦值了
while(pLen != 0)
{
*(skip+(unsigned char)*ptrn++) = pLen--;
}

return skip;
}

// 函數：int* MakeShift(char *, int)
// 目的：根據好後綴規則做預處理，建立一張好後綴表
// 參數：
// ptrn => 模式串P
// PLen => 模式串P長度
// 返回：
// int* - 好後綴表
int* MakeShift(char* ptrn,int pLen)
{
//為好後綴表申請pLen個int的空間
int *shift = (int*)malloc(pLen*sizeof(int));
int *sptr = shift + pLen - 1;//方便給好後綴表進行賦值的指標
char *pptr = ptrn + pLen - 1;//記錄好後綴表邊界位置的指標
char c;

if(shift == NULL)
{
fprintf(stderr,"malloc failed!");
return 0;
}

c = *(ptrn + pLen - 1);//保存模式串中最後一個字元，因為要反復用到它

*sptr = 1;//以最後一個字元為邊界時，確定移動1的距離

pptr--;//邊界移動到倒數第二個字元（這句是我自己加上去的，因為我總覺得不加上去會有BUG，大家試試「abcdd」的情況，即末尾兩位重復的情況）

while(sptr-- != shift)//該最外層循環完成給好後綴表中每一個單元進行賦值的工作
{
char *p1 = ptrn + pLen - 2, *p2,*p3;

//該do...while循環完成以當前pptr所指的字元為邊界時，要移動的距離
do{
while(p1 >= ptrn && *p1-- != c);//該空循環，尋找與最後一個字元c匹配的字元所指向的位置

p2 = ptrn + pLen - 2;
p3 = p1;

while(p3 >= ptrn && *p3-- == *p2-- && p2 >= pptr);//該空循環，判斷在邊界內字元匹配到了什麼位置

}while(p3 >= ptrn && p2 >= pptr);

*sptr = shift + pLen - sptr + p2 - p3;//保存好後綴表中，以pptr所在字元為邊界時，要移動的位置

// PS:在這里我要聲明一句，*sptr = （shift + pLen - sptr） + p2 - p3;
// 大家看被我用括弧括起來的部分，如果只需要計算字元串移動的距離，那麼括弧中的那部分是不需要的。
// 因為在字元串自左向右做匹配的時候，指標是一直向左移的，這里*sptr保存的內容，實際是指標要移動
// 距離，而不是字元串移動的距離。我想SNORT是出於性能上的考慮，才這么做的。
pptr--;//邊界繼續向前移動
}

return shift;
}

// 函數：int* BMSearch(char *, int , char *, int, int *, int *)
// 目的：判斷文本串T中是否包含模式串P
// 參數：
// buf => 文本串T
// blen => 文本串T長度
// ptrn => 模式串P
// PLen => 模式串P長度
// skip => 壞字元表
// shift => 好後綴表
// 返回：
// int - 1表示成功（文本串包含模式串），0表示失敗（文本串不包含模式串）。
int BMSearch(char *buf, int blen, char *ptrn, int plen, int *skip, int *shift)
{
int b_idx = plen;
if (plen == 0)
return 1;
while (b_idx <= blen)//計算字元串是否匹配到了盡頭
{
int p_idx = plen, skip_stride, shift_stride;
while (buf[--b_idx] == ptrn[--p_idx])//開始匹配
{
if (b_idx < 0)
return 0;
if (p_idx == 0)
{
return 1;
}
}
skip_stride = skip[(unsigned char)buf[b_idx]];//根據壞字元規則計算跳躍的距離
shift_stride = shift[p_idx];//根據好後綴規則計算跳躍的距離
b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;//取大者
}
return 0;
}

❸ 解析一哈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演算法很重要。
略知一二！