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算法，并给出了相应代码实现。此外，文章还对该函数的应用场景进行了简单介绍。