求子串当然最经典的就是KMP算法了。brute force算法在leetcode上貌似也有一些技巧。

brute force:

 char* StrStr(const char *str, const char *target) {
if (!*target) return str;
char *p1 = (char*)str, *p2 = (char*)target;
char *p1Adv = (char*)str;
while (*++p2)
p1Adv++; // 这里相当于用这个指针控制外循环为N-M+1次
while (*p1Adv) {
char *p1Begin = p1;
p2 = (char*)target;
while (*p1 && *p2 && *p1 == *p2) {
p1++;
p2++;
}
if (!*p2)
return p1Begin;
p1 = p1Begin + ;
p1Adv++;
}
return NULL;
}

Knuth–Morris–Pratt算法:

 algorithm kmp_search:
input:
an array of characters, S (the text to be searched)
an array of characters, W (the word sought)
output:
an integer (the zero-based position in S at which W is found) define variables:
an integer, m ← (the beginning of the current match in S)
an integer, i ← (the position of the current character in W)
an array of integers, T (the table, computed elsewhere) while m + i < length(S) do
if W[i] = S[m + i] then
if i = length(W) - then
return m
let i ← i +
else
let m ← m + i - T[i]
if T[i] > - then
let i ← T[i]
else
let i ← (if we reach here, we have searched all of S unsuccessfully)
return the length of S

当然关键在于求T这个数组,T[i]就相当于S[0:T[i]] = W[i - T[i], i]。

 algorithm kmp_table:
input:
an array of characters, W (the word to be analyzed)
an array of integers, T (the table to be filled)
output:
nothing (but during operation, it populates the table) define variables:
an integer, pos ← (the current position we are computing in T)
an integer, cnd ← (the zero-based index in W of the next
character of the current candidate substring) (the first few values are fixed but different from what the algorithm
might suggest)
let T[] ← -, T[] ← while pos < length(W) do
(first case: the substring continues)
if W[pos - ] = W[cnd] then
let cnd ← cnd + , T[pos] ← cnd, pos ← pos + (second case: it doesn't, but we can fall back)
else if cnd > 0 then
let cnd ← T[cnd] (third case: we have run out of candidates. Note cnd = 0)
else
let T[pos] ← 0, pos ← pos + 1
04-21 05:59
查看更多