C++中strstr函数的实现方法总结

什么是strstr函数

strstr函数是C/C++中的字符串函数之一，用于在字符串中查找子串。其原型如下：

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

它的功能是在 str1 字符串中查找第一次出现 str2 字符串的位置，如果未找到则返回null。

strstr函数的实现方法

以下是三种strstr函数的实现方法：

方法一：暴力匹配

暴力匹配法就是按顺序比较主串与子串的每一个字符，如果匹配成功，则继续下去；否则就从原先主串与子串匹配的下一个字符重新开始匹配。如果匹配成功，则返回第一次匹配的位置；否则返回 null。该算法的时间复杂度是O(m*n)（m为主串长度，n为子串长度），在处理较小的字符串时效率还不错，但在处理大字符串时效率很低。

char* myStrStr(const char* str1, const char* str2){
    char* cp = (char*)str1;
    char* s1, * s2;
    if (!*str2) return ((char*) str1);

    while (*cp)
    {
        s1 = cp;
        s2 = (char*) str2;
        while (*s1 && *s2 && !(*s1 - *s2)) s1++, s2++;
        if (!*s2) return cp;
        cp++;
    }
    return nullptr;
}

上述代码中，cp为主串中从当前位置开始的字符串，s1为分割后的主串，s2为要查找的子串。

方法二：KMP算法

KMP算法是一种改进的字符串匹配算法，它的核心思想是利用已知信息对下一步匹配位置进行优化，以此减少匹配次数，提高效率。在处理大点的字符串时效率很高，时间复杂度为O(n+m)（m为主串长度，n为子串长度）。

char* myStrStr(const char* str1, const char* str2){
    int len1, len2, next[10000];
    len1 = strlen(str1);
    len2 = strlen(str2);

    int index = -1;
    int i = 0, j = 0;

    if (len2 == 0) return ((char*) str1);

    next[0] = -1;
    while (i < len2)
    {
        if (j == -1 || str2[i] == str2[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

    i = 0, j = 0;
    while (i < len1 && j < len2)
    {
        if (j == -1 || str1[i] == str2[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];    
        }
    }

    if (j == len2) index = i - j;
    else return nullptr;

    return (char*) (str1 + index);
}

上述代码中，str1为主串，str2为子串，next用于存储子串匹配失败时需要跳转的位置。

方法三：Boyer Moore算法

Boyer Moore算法也是一种改进的字符串匹配算法，它的核心思想是在字符串匹配失败时，从后往前匹配，以此减少匹配次数，提高效率。该算法是实际应用中最广泛的字符串查找算法之一。

char* myStrStr(const char* str1, const char* str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    if (len2 == 0) return (char*)str1;

    int index = -1, i = len2 - 1, j = len2 - 1, pos;
    while (i < len1 && j >= 0)
    {
        while (str1[i] != str2[j] && j >= 0)
        {
            pos = myCharInStr(str2, len2, str1[i], j-1);
            if (pos == -1) i += len2;
            else i += len2 - pos - 1;
            j = len2 - 1;
        }
        i--;
        j--;
    }

    if (j == -1) index = i + 1;
    else return nullptr;

    return (char*) (str1 + index);
}

int myCharInStr(const char* str, int len, char c, int pos)
{
    for (int i = pos; i >= 0; i--)
    {
        if (str[i] == c) return i;
    }

    return -1;
}

上述代码中，str1为主串，str2为子串，pos记录在出现不匹配时，子串中下一个字符的匹配位置向后移一位。

示例

示例一

#include<cstring>
#include<iostream>

using namespace std;

char* myStrStr(const char* str1, const char* str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);

    if (len2 == 0) return (char*)str1;

    int index = -1, i = len2 - 1, j = len2 - 1, pos;
    while (i < len1 && j >= 0)
    {
        while (str1[i] != str2[j] && j >= 0)
        {
            pos = myCharInStr(str2, len2, str1[i], j-1);
            if (pos == -1) i += len2;
            else i += len2 - pos - 1;
            j = len2 - 1;
        }
        i--;
        j--;
    }

    if (j == -1) index = i + 1;
    else return nullptr;

    return (char*) (str1 + index);
}

int myCharInStr(const char* str, int len, char c, int pos)
{
    for (int i = pos; i >= 0; i--)
    {
        if (str[i] == c) return i;
    }

    return -1;
}

int main(){
    char a[] = "hello world";
    char b[] = "world";
    char* p = myStrStr(a,b);
    if (p)
        cout << p << endl;
    else
        cout << "not found" << endl;

    return 0;
}

在上述示例中，主串为“hello world”，子串为“world”，通过使用Boyer Moore算法查找子串在主串中的位置，输出结果为“world”。

示例二

#include<cstring>
#include<iostream>

using namespace std;

char* myStrStr(const char* str1, const char* str2)
{
    int len1, len2, next[10000];
    len1 = strlen(str1);
    len2 = strlen(str2);

    int index = -1;
    int i = 0, j = 0;

    if (len2 == 0) return ((char*) str1);

    next[0] = -1;
    while (i < len2)
    {
        if (j == -1 || str2[i] == str2[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];
        }
    }

    i = 0, j = 0;
    while (i < len1 && j < len2)
    {
        if (j == -1 || str1[i] == str2[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];    
        }
    }

    if (j == len2) index = i - j;
    else return nullptr;

    return (char*) (str1 + index);
}

int main(){
    char a[] = "hello world";
    char b[] = "world";
    char* p = myStrStr(a,b);
    if (p)
        cout << p << endl;
    else
        cout << "not found" << endl;

    return 0;
}

在上述示例中，主串为“hello world”，子串为“world”，通过使用KMP算法查找子串在主串中的位置，输出结果为“world”。