在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進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
