Leetcode | substr()

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

brute force：

 1 char* StrStr(const char *str, const char *target) {
 2   if (!*target) return str;
 3   char *p1 = (char*)str, *p2 = (char*)target;
 4   char *p1Adv = (char*)str;
 5   while (*++p2)
 6     p1Adv++; // 这里相当于用这个指针控制外循环为N-M+1次
 7   while (*p1Adv) {
 8     char *p1Begin = p1;
 9     p2 = (char*)target;
10     while (*p1 && *p2 && *p1 == *p2) {
11       p1++;
12       p2++;
13     }
14     if (!*p2)
15       return p1Begin;
16     p1 = p1Begin + 1;
17     p1Adv++;
18   }
19   return NULL;
20 }

Knuth–Morris–Pratt算法：

 1 algorithm kmp_search:
 2     input:
 3         an array of characters, S (the text to be searched)
 4         an array of characters, W (the word sought)
 5     output:
 6         an integer (the zero-based position in S at which W is found)
 7 
 8     define variables:
 9         an integer, m ← 0 (the beginning of the current match in S)
10         an integer, i ← 0 (the position of the current character in W)
11         an array of integers, T (the table, computed elsewhere)
12 
13     while m + i < length(S) do
14         if W[i] = S[m + i] then
15             if i = length(W) - 1 then
16                 return m
17             let i ← i + 1
18         else
19             let m ← m + i - T[i]
20             if T[i] > -1 then
21                 let i ← T[i]
22             else
23                 let i ← 0
24             
25     (if we reach here, we have searched all of S unsuccessfully)
26     return the length of S

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

 1 algorithm kmp_table:
 2     input:
 3         an array of characters, W (the word to be analyzed)
 4         an array of integers, T (the table to be filled)
 5     output:
 6         nothing (but during operation, it populates the table)
 7 
 8     define variables:
 9         an integer, pos ← 2 (the current position we are computing in T)
10         an integer, cnd ← 0 (the zero-based index in W of the next 
11 character of the current candidate substring)
12 
13     (the first few values are fixed but different from what the algorithm 
14 might suggest)
15     let T[0] ← -1, T[1] ← 0
16 
17     while pos < length(W) do
18         (first case: the substring continues)
19         if W[pos - 1] = W[cnd] then
20             let cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1
21 
22         (second case: it doesn't, but we can fall back)
23         else if cnd > 0 then
24             let cnd ← T[cnd]
25 
26         (third case: we have run out of candidates.  Note cnd = 0)
27         else
28             let T[pos] ← 0, pos ← pos + 1