[LintCode]文字列検索
9809 ワード
暴力解法(O(mn):
KMP(O(m + n)):
1 class Solution {
2 public:
3 /**
4 * Returns a index to the first occurrence of target in source,
5 * or -1 if target is not part of source.
6 * @param source string to be scanned.
7 * @param target string containing the sequence of characters to match.
8 */
9 int strStr(const char *source, const char *target) {
10 // write your code here
11 if (!source || !target) return -1;
12 int m = strlen(source), n = strlen(target);
13 for (int i = 0; i < m - n + 1; i++) {
14 int j = 0;
15 for (; j < n; j++)
16 if (source[i + j] != target[j])
17 break;
18 if (j == n) return i;
19 }
20 return -1;
21 }
22 };
KMP(O(m + n)):
1 class Solution {
2 public:
3 /**
4 * Returns a index to the first occurrence of target in source,
5 * or -1 if target is not part of source.
6 * @param source string to be scanned.
7 * @param target string containing the sequence of characters to match.
8 */
9 int strStr(const char *source, const char *target) {
10 // write your code here
11 if (!source || !target) return -1;
12 int m = strlen(source), n = strlen(target);
13 if (!n) return 0;
14 vector<int> lps = kmpProcess(target);
15 for (int i = 0, j = 0; i < m; ) {
16 if (source[i] == target[j]) {
17 i++;
18 j++;
19 }
20 if (j == n) return i - j;
21 if (i < m && source[i] != target[j]) {
22 if (j) j = lps[j - 1];
23 else i++;
24 }
25 }
26 return -1;
27 }
28 private:
29 vector<int> kmpProcess(const char* target) {
30 int n = strlen(target);
31 vector<int> lps(n, 0);
32 for (int i = 1, len = 0; i < n; ) {
33 if (target[i] == target[len])
34 lps[i++] = ++len;
35 else if (len) len = lps[len - 1];
36 else lps[i++] = 0;
37 }
38 return lps;
39 }
40 };