字符串搜索算法
维基百科,自由的 encyclopedia
字符串搜索算法(String searching algorithms)又称字符串比对算法(string matching algorithms)是一种搜索算法,是字符串算法中的一类,用以试图在一长字符串或文章中,找出其是否包含某一个或多个字符串,以及其位置。
最直观的解法是比对,如下例中,在字符串haystack中找出字符串needle
char* haystack;
char* needle;
int hlen, nlen, found;
int i,j,k;
found = 0;
hlen = strlen(haystack);
nlen = strlen(needle);
for (i = 0; i < hlen; ++i) {
for (j = 0; j < nlen; ++j) {
if (haystack[i+j] != needle[j]) break;
if (j == nlen - 1) found = 1;
};
};
return found;
上例中,若字符串needle存在于字符串haystack中,则传回1,否则传回0。
但是此直观算法的复杂度为 O(mn),其中haystack的长度为n、needle的长度为m,所以另有更快速的算法。