您好，登录后才能下订单哦！
密码登录
登录注册
点击 登录注册 即表示同意《亿速云用户服务条款》
在C语言编程中，字符串处理是一个非常重要的部分。strstr函数是C标准库中的一个常用函数，用于在一个字符串中查找另一个字符串的首次出现位置。本文将详细介绍如何用C语言模拟实现strstr函数，并通过代码示例和详细解释帮助读者理解其实现原理。
strstr函数的功能strstr函数的原型如下：
char *strstr(const char *haystack, const char *needle);
haystack：被查找的字符串。needle：要查找的子字符串。函数的功能是在haystack字符串中查找needle字符串的首次出现位置。如果找到，则返回指向该位置的指针；如果未找到，则返回NULL。
要实现strstr函数，我们需要模拟其查找过程。具体步骤如下：
haystack字符串：从haystack的第一个字符开始，逐个字符进行匹配。needle字符串：对于haystack中的每一个字符，尝试与needle的第一个字符匹配。如果匹配成功，则继续匹配needle的下一个字符，直到needle的所有字符都匹配成功。needle的所有字符都匹配成功，则返回当前haystack中的匹配位置。NULL：如果遍历完haystack仍未找到匹配的needle，则返回NULL。下面是一个简单的strstr函数的模拟实现：
#include <stdio.h>
char *my_strstr(const char *haystack, const char *needle) {
if (*needle == '\0') {
return (char *)haystack;
}
const char *p1;
const char *p2;
const char *p1_advance = haystack;
for (p2 = &needle[1]; *p2; ++p2) {
p1_advance++;
}
for (p1 = haystack; *p1_advance; p1_advance++) {
char *p1_old = (char *)p1;
p2 = needle;
while (*p1 && *p2 && *p1 == *p2) {
p1++;
p2++;
}
if (!*p2) {
return p1_old;
}
p1 = p1_old + 1;
}
return NULL;
}
int main() {
const char *haystack = "Hello, world!";
const char *needle = "world";
char *result = my_strstr(haystack, needle);
if (result) {
printf("'%s' found in '%s' at position %ld\n", needle, haystack, result - haystack);
} else {
printf("'%s' not found in '%s'\n", needle, haystack);
}
return 0;
}
边界条件处理：如果needle为空字符串，则直接返回haystack的起始地址。
if (*needle == '\0') {
return (char *)haystack;
}
计算needle的长度：通过遍历needle字符串，计算其长度，并确定p1_advance的初始位置。
const char *p2;
const char *p1_advance = haystack;
for (p2 = &needle[1]; *p2; ++p2) {
p1_advance++;
}
遍历haystack：使用p1指针遍历haystack，并在每次循环中尝试匹配needle。
for (p1 = haystack; *p1_advance; p1_advance++) {
char *p1_old = (char *)p1;
p2 = needle;
while (*p1 && *p2 && *p1 == *p2) {
p1++;
p2++;
}
if (!*p2) {
return p1_old;
}
p1 = p1_old + 1;
}
返回匹配结果：如果找到匹配的needle，则返回匹配位置的指针；否则返回NULL。
return NULL;
为了验证我们的my_strstr函数是否正确，我们可以编写一些测试用例：
int main() {
const char *haystack = "Hello, world!";
const char *needle1 = "world";
const char *needle2 = "foo";
const char *needle3 = "";
char *result1 = my_strstr(haystack, needle1);
char *result2 = my_strstr(haystack, needle2);
char *result3 = my_strstr(haystack, needle3);
if (result1) {
printf("'%s' found in '%s' at position %ld\n", needle1, haystack, result1 - haystack);
} else {
printf("'%s' not found in '%s'\n", needle1, haystack);
}
if (result2) {
printf("'%s' found in '%s' at position %ld\n", needle2, haystack, result2 - haystack);
} else {
printf("'%s' not found in '%s'\n", needle2, haystack);
}
if (result3) {
printf("'%s' found in '%s' at position %ld\n", needle3, haystack, result3 - haystack);
} else {
printf("'%s' not found in '%s'\n", needle3, haystack);
}
return 0;
}
运行上述测试代码，输出如下：
'world' found in 'Hello, world!' at position 7
'foo' not found in 'Hello, world!'
'' found in 'Hello, world!' at position 0
从输出结果可以看出，我们的my_strstr函数能够正确地找到needle字符串在haystack中的位置，并且在needle为空字符串时也能正确处理。
虽然上述实现能够正确工作，但在某些情况下可能存在性能问题。例如，当haystack和needle都非常长时，逐字符匹配的效率可能会较低。为了提高性能，可以考虑使用更高效的字符串匹配算法，如KMP算法或Boyer-Moore算法。
KMP算法（Knuth-Morris-Pratt算法）是一种高效的字符串匹配算法，其核心思想是通过预处理needle字符串，构建一个部分匹配表（也称为“失败函数”），从而在匹配过程中避免不必要的回溯。
以下是使用KMP算法实现的strstr函数：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void computeLPSArray(const char *needle, int M, int *lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (needle[i] == needle[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
char *my_strstr_kmp(const char *haystack, const char *needle) {
int M = strlen(needle);
int N = strlen(haystack);
if (M == 0) {
return (char *)haystack;
}
int *lps = (int *)malloc(sizeof(int) * M);
computeLPSArray(needle, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if (needle[j] == haystack[i]) {
j++;
i++;
}
if (j == M) {
free(lps);
return (char *)(haystack + i - j);
} else if (i < N && needle[j] != haystack[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
free(lps);
return NULL;
}
int main() {
const char *haystack = "ABABDABACDABABCABAB";
const char *needle = "ABABCABAB";
char *result = my_strstr_kmp(haystack, needle);
if (result) {
printf("'%s' found in '%s' at position %ld\n", needle, haystack, result - haystack);
} else {
printf("'%s' not found in '%s'\n", needle, haystack);
}
return 0;
}
构建部分匹配表：computeLPSArray函数用于构建needle字符串的部分匹配表lps。
void computeLPSArray(const char *needle, int M, int *lps) {
int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (needle[i] == needle[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
}
}
}
匹配过程：my_strstr_kmp函数使用KMP算法进行字符串匹配。
char *my_strstr_kmp(const char *haystack, const char *needle) {
int M = strlen(needle);
int N = strlen(haystack);
if (M == 0) {
return (char *)haystack;
}
int *lps = (int *)malloc(sizeof(int) * M);
computeLPSArray(needle, M, lps);
int i = 0;
int j = 0;
while (i < N) {
if (needle[j] == haystack[i]) {
j++;
i++;
}
if (j == M) {
free(lps);
return (char *)(haystack + i - j);
} else if (i < N && needle[j] != haystack[i]) {
if (j != 0) {
j = lps[j - 1];
} else {
i++;
}
}
}
free(lps);
return NULL;
}
测试与验证：通过测试用例验证KMP算法的正确性。
int main() {
const char *haystack = "ABABDABACDABABCABAB";
const char *needle = "ABABCABAB";
char *result = my_strstr_kmp(haystack, needle);
if (result) {
printf("'%s' found in '%s' at position %ld\n", needle, haystack, result - haystack);
} else {
printf("'%s' not found in '%s'\n", needle, haystack);
}
return 0;
}
运行上述测试代码，输出如下：
'ABABCABAB' found in 'ABABDABACDABABCABAB' at position 10
从输出结果可以看出，KMP算法能够正确地找到needle字符串在haystack中的位置，并且在处理长字符串时具有较高的效率。
本文详细介绍了如何用C语言模拟实现strstr函数，并通过代码示例和详细解释帮助读者理解其实现原理。我们还介绍了KMP算法，并通过代码示例展示了如何使用KMP算法优化字符串匹配的性能。希望本文能够帮助读者更好地理解字符串匹配的原理，并在实际编程中灵活运用这些知识。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。