首页 > 代码库 > Implement strStr()
Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
方法一：暴力破解，O(mn)，超时，写了这段代码，估计面试直接出局。
1 class Solution { 2 public: 3 char *strStr(char *haystack, char *needle) { 4 if( !haystack || !needle ) return 0; 5 while( *haystack ) { 6 char* p1 = haystack; 7 char* p2 = needle; 8 while( *p1 && *p2 && *p1 == *p2 ) ++p1, ++p2; 9 if( !*p2 ) return haystack;10 ++haystack;11 }12 return 0;13 }14 };
方法二：对上面进行优化，AC
1 class Solution { 2 public: 3 char *strStr(char *haystack, char *needle) { 4 if( !haystack || !needle ) return 0; 5 if( !*needle ) return haystack; 6 int len1 = strlen(haystack); 7 int len2 = strlen(needle); 8 for(int i=0; i+len2<=len1; ++i) { //保证i后面的字符串长度>=needle的长度 9 if( haystack[i] != *needle ) continue; //第一个字母不匹配，跳过10 char* p1 = haystack+i;11 char* p2 = needle;12 while( *p1 && *p2 && *p1 == *p2 ) ++p1,++p2;13 if( !*p2 ) return haystack+i;14 }15 return 0;16 }17 };
方法三：KMP算法，关键在于理解和求next数组。假设pattern字符串为p0p1p2p3....pn-1，长度为n，那么有
当 j = 0 时，next[j] = -1
当存在 max{ k | 0 < k < j 且 ‘p0p1p2...pk-1‘ = ‘pj-k...pj-1‘ } 时，next[j] = k
其他情况 next[j] = 0
j 0 1 2 3 4 5 6
pattern a b a a b c a
next[j] -1 0 0 1 1
这里要求next[5] ，首先看子串p0p1p2p3p4 = abaab，我们发现 p0p1 = ab ，p3p4 = ab，此时k = 2，那么next[5] = 2，即当pattern[5]不匹配时，那么pattern[3..4]是匹配的，而pattern[0..1] = pattern[3..4]，故下次应该匹配的字符应该是pattern[2]，其下标也就是next[5]的值
如何求解next[j]的值？
假设已经知道 next[j-1] = k，那么说明当pattern[j-1]不匹配的时候，那么应该与pattern[k]比较，也告诉我们 ‘p0p1p2...pk-1‘ = ‘pj-k-1...pj-2‘
如果 pk = pj-1 ，那么就有 ‘p0p1p2...pk-1pk‘ = ‘pj-k-1...pj-2pj-1‘ ，说明当pattern[j]不匹配时，那么可以与pattern[k+1]比较，即next[j] = k+1 = next[j-1]+1
如果 pk != pj-1，那么说明 ‘p0p1p2...pk-1pk‘ ！= ‘pj-k-1...pj-2pj-1‘ ，需要继续需找匹配的最长前缀和后缀，需找的方法如下：
1. k = next[j-1]，比较pk 与 pj-1，若相等，那么next[j] = next[j-1] + 1，若不等转2
2. k1 = next[k]，继续比较pk1 与 pj-1，若相等那么next[j] = next[k] + 1，若不等转3
3. k2 = next[k1]，继续比较pk2 与 pj-1，若相等那么next[j] = next[k1] + 1，若不等转...
......
n. kn = next[kn-1]，假设此时pkn = pj-1，那说明 ‘p0p1...pkn‘ = ‘pj-kn-1...pj-1‘，那么如果pattern[j]不匹配，可于pattern[kn+1]匹配，即next[j] = next[kn-1] + 1 = kn + 1;
注：若最后依然没有找到相等的，即kn = -1，此时next[j] = 0
代码如下：
1 class Solution { 2 public: 3 vector<int> getNext(char *str) { 4 int len = strlen(str); 5 vector<int> next(len, 0); 6 next[0] = -1; //初始化 7 for(int i=1; i<len; ++i) { //主要思路请看讲解 8 int k = next[i-1]; 9 while( k!=-1 && str[k] != str[i-1] ) k = next[k]; //k=-1或找到pk == pi-1时终止10 next[i] = k+1;11 }12 return next;13 }14 15 char *strStr(char *haystack, char *needle) {16 if( !haystack || !needle ) return 0;17 if( !*needle ) return haystack;18 vector<int> next = getNext(needle);19 int i=0, j=0;20 while( haystack[i] && needle[j] ) {21 if( haystack[i] == needle[j] ) { //如果相等，ij同时后移22 ++i,++j;23 }24 else { //不等25 j = next[j]; //haystack[i] 应该与 needle[j]比较26 if( j==-1 ) ++i, j=0; //如果j为-1,说明haystack[i]不存在needle中,那么直接跳过27 }28 }29 if( !needle[j] ) return haystack+i-j; //如果j指向末尾了，说明找到了30 else return 0;31 }32 };
Implement strStr()