字符串查找子串

一、字符串查找子串函数

在编写字符串处理程序时，字符串查找子串函数是非常实用的。在C++中，常用的字符串查找子串函数为std::string::find()。这个函数可以用来查找字符串中的子串。例如：

std::string str = "hello world";
int index = str.find("world");

这个例子中，我们定义了一个字符串str，并使用std::string::find()函数查找其中的子串”world”，得到了这个子串在字符串中的位置。

在Python中，可以使用字符串自带的方法find()来查找子串，例如：

str = "hello world"
index = str.find("world")

二、字符串查找子串的个数

有时候我们需要统计字符串中子串出现的次数，C++和Python都提供了方法用来实现这个功能。

在C++中，我们可以使用std::string::find()函数和循环来查找字符串中子串出现的次数。例如：

std::string str = "hello world";
std::string substr = "l";
int count = 0;
size_t pos = 0;
while ((pos = str.find(substr, pos)) != std::string::npos) {
    ++count;
    pos += substr.length();
}

这个代码段中，我们定义了一个变量count来保存查找到的子串的个数，然后使用循环和std::string::find()函数来查找每个子串出现的位置，并将count加一。

在Python中，可以使用字符串自带的方法count()来查找子串的个数。例如：

str = "hello world"
substr = "l"
count = str.count(substr)

三、字符串查找子串可以使用index

在Python中，字符串自带的方法index()也可以用来查找子串。与find()函数不同的是，当子串不存在时，index()函数会抛出一个异常，而find()函数会返回std::string::npos。例如：

str = "hello world"
index = str.index("world")

四、字符串查找子串出现次数

除了统计子串出现的次数外，有时候我们还需要知道每个子串出现的位置。在C++中，可以使用std::string::find()函数和std::vector来实现这个功能。例如：

std::string str = "hello world";
std::string substr = "l";
size_t pos = 0;
std::vector indices;
while ((pos = str.find(substr, pos)) != std::string::npos) {
    indices.push_back(pos);
    pos += substr.length();
}

这个代码段中，我们定义了一个std::vector来保存查找到的子串的位置，然后使用循环和std::string::find()函数来查找每个子串出现的位置，并将位置保存到vector中。

在Python中，可以使用字符串自带的方法finditer()来查找子串出现的位置。这个方法返回一个生成器，可以使用for循环来遍历每个子串的位置。例如：

str = "hello world"
substr = "l"
indices = [m.start() for m in re.finditer(substr, str)]

五、字符串查找子串最快算法

在C++中，可以使用KMP算法来实现字符串查找子串功能。KMP算法是一种线性时间复杂度的算法，比std::string::find()函数更快，特别是对于长字符串和重复出现的子串。KMP算法的基本思想是在匹配的过程中，当发现不匹配时，不需要回溯，而是通过已经匹配的信息，直接跳过一部分文本。

以下是KMP算法的实现代码：

void computeLPSArray(std::string substr, int* lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < substr.length()) {
        if (substr[i] == substr[len]) {
            ++len;
            lps[i] = len;
            ++i;
        } else {
            if (len != 0) {
                len = lps[len-1];
            } else {
                lps[i] = 0;
                ++i;
            }
        }
    }
}
int KMP(std::string str, std::string substr) {
    int n = str.length();
    int m = substr.length();
    int lps[m];
    computeLPSArray(substr, lps);
    int i = 0;
    int j = 0;
    while (i < n) {
        if (substr[j] == str[i]) {
            ++i;
            ++j;
        }
        if (j == m) {
            return i-j;
        } else if (i < n && substr[j] != str[i]) {
            if (j != 0) {
                j = lps[j-1];
            } else {
                ++i;
            }
        }
    }
   return -1;
}

在Python中，也可以使用KMP算法来实现字符串查找子串功能。例如：

def computeLPSArray(substr):
    len = 0
    lps = [0] * len(substr)
    i = 1
    while i < len(substr):
        if substr[i] == substr[len]:
            len += 1
            lps[i] = len
            i += 1
        else:
            if len != 0:
                len = lps[len-1]
            else:
                lps[i] = 0
                i += 1
    return lps
def KMP(str, substr):
    n = len(str)
    m = len(substr)
    lps = computeLPSArray(substr)
    i = 0
    j = 0
    while i < n:
        if substr[j] == str[i]:
            i += 1
            j += 1
        if j == m:
            return i-j
        elif i < n and substr[j] != str[i]:
            if j != 0:
                j = lps[j-1]
            else:
                i += 1
    return -1

六、字符串查找子串算法

除了KMP算法，还有其他算法可以用来实现字符串查找子串功能。例如，Brute-Force算法就是一种朴素的算法，在每个位置都尝试查找子串，并比较字母。这种算法的时间复杂度为O(mn)，其中m是子串长度，n是字符串长度，效率较低。

以下是Brute-Force算法的实现代码：

int BruteForce(std::string str, std::string substr) {
    int n = str.length();
    int m = substr.length();
    for (int i=0; i<=n-m; ++i) {
        int j;
        for (j=0; j<m; ++j) {
            if (str[i+j] != substr[j]) {
                break;
            }
        }
        if (j == m) {
            return i;
        }
    }
    return -1;
}

七、字符串查找子串C代码

以下是使用std::string::find()函数实现字符串查找子串的C代码：

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

int main() {
    char str[20] = "hello world";
    char substr[10] = "world";
    char* p = strstr(str, substr);
    if (p) {
        printf("%s found at position %d.\n", substr, p-str);
    } else {
        printf("%s not found.\n", substr);
    }
    return 0;
}

八、字符串查找子串Python

以下是使用字符串自带方法find()实现字符串查找子串的Python代码：

str = "hello world"
substr = "world"
index = str.find(substr)
if index != -1:
    print(substr, "found at position", index)
else:
    print(substr, "not found.")