深圳自适应网站制作,帝国软件怎么做网站,微网站建设套餐,济南住建官网Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack. 此题我觉得并不是真要你写出kmp算法。 指针暴力法我觉得可能是考察点。而且要accept的话#xff0c;必须要忽略后面一段不可能匹配的串。…Implement strStr(). Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack. 此题我觉得并不是真要你写出kmp算法。 指针暴力法我觉得可能是考察点。而且要accept的话必须要忽略后面一段不可能匹配的串。指针的操作要非常小心。 Of course, you can demonstrate to your interviewer that this problem can be solved using known efficient algorithms such as Rabin-Karp algorithm, KMP algorithm, and the Boyer-Moore algorithm. Since these algorithms are usually studied in advanced algorithms class, for an interview it is sufficient to solve it using the most direct method — The brute force method. 非指针代码很好小很难有错。最长扫描n1-n21个就够了。 1 class Solution {2 public:3 char *strStr(char *haystack, char *needle) {4 if (haystack NULL || needle NULL) return NULL;5 int n1 strlen(haystack);6 int n2 strlen(needle);7 int j; 8 9 for (int i 0; i n1 - n2 1; i) {
10 j 0;
11 while (j n2 needle[j] haystack[i j]) j;
12 if (j n2) return haystack i;
13 }
14 return NULL;
15 }
16 }; c指针代码 1 class Solution {2 public:3 char *strStr(char *haystack, char *needle) {4 if (haystack NULL || needle NULL) return NULL;5 if (*needle \0) return haystack;6 char *ph haystack, *pn needle, *count ph, *tmp;7 while (*pn) {8 if (!*count) return NULL;9 pn;
10 count;
11 }
12 if (*needle) count--;
13 while (*count) {
14 pn needle;
15 tmp ph;
16 while (*pn *tmp *pn *tmp) {
17 pn; tmp;
18 }
19 if (!*pn) return ph;
20 ph;
21 count;
22 }
23
24 return NULL;
25 }
26 }; 如果是needle是空串返回应该是haystack整个串。 最长扫描n1-n21个就够了。所以要让count循环m-1次。优化后的代码如下 1 class Solution {2 public:3 char *strStr(char *haystack, char *needle) {4 if (*needle \0) return haystack;5 char *ph haystack, *pn needle, *count ph, *tmp;6 while (*pn) {7 if (!*count) return NULL;8 count;9 }
10 while (*count) {
11 pn needle;
12 tmp ph;
13 while (*pn *tmp *pn *tmp) {
14 pn; tmp;
15 }
16 if (!*pn) return ph;
17 ph;
18 count;
19 }
20
21 return NULL;
22 }
23 }; kmp算法的话直接看wiki就好。看完也实现一遍。 Partial match 数组里面存的是当前位置的前缀等于整个匹配串的某个前缀。 比如ABCDABC第二个B红色对应的值就是1绿色. 匹配失败后假设haystack的当前位置是i匹配到ij失败了假设就匹配到第二个B失败。那么就要j就要指向第一个B那里然后i就要跳到第二个A也就是i i j - P[j]. 1 class Solution {2 public:3 char *strStr(char *haystack, char *needle) {4 if (haystack NULL || needle NULL) return NULL;5 if (*needle \0) return haystack;6 7 int n1 strlen(haystack), n2 strlen(needle), count 0;8 vectorint kmp(n2, 0);9 kmp[0] -1;
10
11 for (int i 2; i n2; ) {
12 if (needle[i - 1] needle[count]) {
13 count;
14 kmp[i] count;
15 } else if (count 0) {
16 count kmp[count];
17 } else {
18 kmp[i] 0;
19 }
20 }
21
22 for (int i 0, j 0; i j n1; ) {
23 if (haystack[i j] needle[j]) {
24 j;
25 if (j n2) return haystack i;
26 } else if (kmp[j] 0) {
27 i i j - kmp[j];
28 j kmp[j];
29 } else {
30 j 0;
31 i;
32 }
33 }
34
35 return NULL;
36 }
37 }; 前面也有摘过KMP算法。 建立表的算法的复杂度是 O(n)其中 n 是 W 的长度。除去一些初始化的工作所有工作都是在 while 循环中完成的足够说明这个循环执行用了 O(n) 的时间同时还会检查 pos 和 pos - cnd 的大小。在第一个分支里pos - cnd 被保留而 pos 与 cnd 同时递增自然pos 增加了。在第二个分支里cnd 被 T[cnd] 所替代即以上总是严格低于 cnd从而增加了 pos - cnd。在第三个分支里pos 增加了而 cnd 没有所以 pos 和 pos - cnd 都增加了。因为 pos ≥ pos - cnd即在每一个阶段要么 pos 增加要么 pos 的一个下界增加所以既然此算法只要有 pos n 就终止了这个循环必然最多在 2n 次迭代后终止, 因为 pos - cnd 从 1 开始。因此建立表的算法的复杂度是 O(n)。转载于:https://www.cnblogs.com/linyx/p/3728708.html
