字串搜尋演算法

字串搜尋演算法（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，所以另有更快速的算法。