字符串搜索算法
2020-05-12 01:37:40
字符串搜索算法(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 != needle) break; if (j == nlen - 1) found = 1; };};return found;
上例中,若字符串needle存在于字符串haystack中,则传回1,否则传回0。
但是此直观算法的复杂度为 O(mn),其中haystack的长度为n、needle的长度为m,所以另有更快速的算法。
令 为模式的长度, 为要搜索的字符串长度, 为字母表长度。