strstr函數詳解

一、函數功能

strstr函數是C語言提供的字符串處理函數之一，其作用是檢索在一個字符串中是否包含另一個子字符串，並返回該子字符串在主字符串中的地址。

二、函數原型

char *strstr(const char *str1, const char *str2);

其中，str1為主字符串，str2為子字符串，函數返回值為指向第一次出現子串的指針。

三、函數實現

1. 暴力匹配算法

暴力匹配算法又被稱為樸素匹配算法，採用逐個比較主字符串和子字符串中的字符的方法，若匹配成功則返回主字符串當前位置指針。

char* my_strstr(const char* str1, const char* str2)
{
    while(*str1)
    {
        const char* p1 = str1;
        const char* p2 = str2;
        while(*p1 && *p2 && !(*p1 - *p2))
        {
            p1++;
            p2++;
        }
        if(!*p2)
        {
            return (char*)str1;
        }
        str1++;
    }
    return NULL;
}

2. KMP算法

KMP算法利用字符串的前綴和後綴的公共部分，避免了暴力算法中大量的回溯操作，從而提高匹配效率。

void getNext(char *T,int *next){
    int i=1,j=0;
    next[1]=0;
    while(i<strlen(T)){
        if(j==0||T[i-1]==T[j-1]){
            ++i;
            ++j;
            next[i]=j;
        }
        else{
            j=next[j];
        }
    }
}
char *KMP(char *S,char *T,int pos,int *next){
    int i,j;
    i=pos;j=1;
    while(i<=strlen(S)&&jstrlen(T)){
        return S+pos;
    }
    else{
        return NULL;
    }
}

3.Boyer-Moore算法

Boyer-Moore算法是一種啟發式算法，它根據模式串最後一個字符在主串中出現的位置，計算出向右移動的步數，從而實現快速匹配。

#define max(x,y) (x>y?x:y)
void pre_bmBc(char *x,int m,int bmBc[]){
    int i;
    for(i=0;i<256;i++){
        bmBc[i]=m;
    }
    for(i=0;i=0;i--){
        j=i;
        while(j>=0&&x[j]==x[m-1-i+j]){
            --j;
        }
        suffix[i]=i-j;
    }
}
void pre_bmGs(char *x,int m,int bmGs[]){
    int i,j,suffix[max_length];
    pre_suffix(x,m,suffix);
    for(i=0;i=-1;i--){
        if(i==-1||suffix[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-suffix[i]]=m-1-i;
    }
}
char *BoyerMoore(char *s,char *x){
    int i,j;
    int m=strlen(x);
    int n=strlen(s);
    int bmBc[256],bmGs[max_length];
    pre_bmBc(x,m,bmBc);
    pre_bmGs(x,m,bmGs);
    j=0;
    while(j=0&&x[i]==s[i+j];--i){
            ;
        }
        if(i<0){
            return s+j;
            j+=bmGs[0];
        }
        else{
            j+=max(bmGs[i],bmBc[s[i+j]]-m+i+1);
        }
    }
    return NULL;
}

四、函數應用

strstr函數常用於字符串查找操作，如字符串替換、字符串匹配、文本搜索等相關應用。

#include 
#include 
int main() {
   char str[80] = "this is a test string";
   char *ptr;
   ptr = strstr(str, "test");// 查找子字符串
   if(ptr) {
      printf("test is found at position %ld\n", ptr-str);// 返回字符串中的位置
   } else {
      printf("test not found\n");
   }
   return 0;
}

五、總結

本文詳細介紹了C語言中的strstr函數及其實現算法，包括暴力匹配算法、KMP算法和Boyer-Moore算法，並給出了相應代碼實現。此外，文章還對該函數的應用場景進行了簡單介紹。