每周一道算法浅析（寻找子字符串）

题：判断一个字符串是否包含另一个字符串（寻找下标、寻找包涵几个子串等）

看到问题首先想到循环一下就解决了，循环比对没问题

bool test1(char *contentChars, char *itemChars) { bool searchSucc = false; int searchCount = 0; for (int i = 0; i < strlen(contentChars); i ++) { for (int j = i; j < strlen(contentChars); j ++) { if (contentChars[j] == itemChars[j - i]) { if (j - i >= strlen(itemChars)) { searchCount ++; searchSucc = true; break; } } else { break; } } } return searchSucc; }

这样解题是可以解的，可以看到复杂度为n*m，那有没有别的解法可以优化一下。

所以引出了KMP算法，这里不解释KMP算法的原理（网上有很多解释，可以去搜一下），直接上代码

void buildNext(const char *T, int Next[]) { int i,j; Next[0] = -1; j = Next[1] = 0; for (i = 2; i < strlen(T); i++){ while (j > 0 && T[i-1] != T[j]) j = Next[j]; if (T[i-1] == T[j]) j++; Next[i] = j; } } bool stringContains(char *contentChars, char *itemChars) { unsigned long zLength = strlen(contentChars); unsigned long length = strlen(itemChars); int Next[128] = {0}; buildNext(itemChars, Next); int i,j; i = j = 0; bool searchSucc = false; int searchCount = 0; int rollCount = 0; while (i < zLength) { rollCount ++; if (contentChars[i] == itemChars[j]) { i ++; j ++; if (j >= length) { searchSucc = true; searchCount ++; //找到，是否继续寻找 bool continueSearch = true; if (continueSearch) { j = Next[j - 1] + 1; } else { break; } } } else { i = i + (j == 0 ? 1 : 0); j = j > 0 ? Next[j] : 0; } } printf("寻找子字符串【%s】%s，共循环%d次，字符串长度%lu，共找到%d个",itemChars, searchSucc ? "成功" : "失败", rollCount, zLength, searchCount); return searchSucc; }

上面就是利用KMP算法进行查找子字符串