LeetCode028 Implement strStr()

LeetCode028 Implement strStr()

详细见：leetcode/problems/implement-strstr

Java Solution: github

package leetcode;public class P028_ImplementStrStr {//AC 13ms 34.88%static class Solution {public int strStr(String s, String p) {int sn = s == null ? 0 : s.length();int pn = p == null ? 0 : p.length();//pn == 0, p match at index 0if (pn == 0) return 0;//sn == 0 and pn > 0 can not matchif (sn == 0) return -1;int si = 0, pi = 0, next[] = getNext(p, pn);while (si < sn) {if (s.charAt(si) == p.charAt(pi)) {si ++;pi ++;if (pi == pn) break;} else if (next[pi] == -1) {si ++;} else pi = next[pi];}return pi == pn ? si - pn : - 1;}public int[] getNext(String p, int pn) {//return short pif (pn < 2) return new int[] {-1};int bi = 0, fi = 2, next[] = new int[pn];next[0] = -1;next[1] = 0;while (fi < pn) {if (p.charAt(fi - 1) == p.charAt(bi)) {next[fi ++] = ++ bi;} else if (bi <= 0) {next[fi ++] = 0;} else bi = next[bi];}return next;}}
}

C Solution: github

/*url: leetcode/problems/implement-strstr/strStr_back:    6ms 36.36%strStr_kmp:     3ms 49.82%
*/#include <stdio.h>
#include <stdlib.h>
#include <string.h>void print_array(int * nums, int numsSize) {int i = 0;for (i = 0; i < numsSize; i ++)printf("%d ", *(nums + i));printf("rn");
}int* _get_next(char* p, int pn) {int bi = 0, fi = 2, * next = NULL;if (pn < 2) {//return short pnext = (int *) malloc(sizeof(int) * 1);next[0] = -1;return next;}next = (int *) malloc(sizeof(int) * pn);next[0] = -1;next[1] = 0;while (fi < pn)if (*(p + fi - 1) == *(p + bi)) {next[fi ++] = ++ bi;} else if (bi > 0) {bi = next[bi];} else next[fi ++] = 0;return next;
}int strStr_kmp(char* s, char* p) {int sn = s == NULL ? 0 : strlen(s);int pn = p == NULL ? 0 : strlen(p);int * next = NULL;int si = 0, pi = 0;if (pn == 0) return 0;if (sn == 0) return -1;next = _get_next(p, pn);while (si < sn) {if (*(s + si) == *(p + pi)) {si ++;pi ++;if (pi == pn) break;} else if (next[pi] == -1) {si ++;} else pi = next[pi];}free(next);return pi == pn ? si - pn : -1;
}int strStr_back(char* s, char* p) {int i = 0, j = 0;char sc = '', pc = '';if (s == NULL || p == NULL)return s == NULL && p == NULL;while (1) {sc = *(s + i);j = 0;while (1) {pc = *(p + j);sc = *(s + i + j);if (pc == '') break;if (sc == '') break;if (pc != *(s + i + j)) break;j ++;}if (pc == '') return i;if (sc == '') return -1;i ++;}return -1;
}int strStr(char* s, char* p) {return strStr_kmp(s, p);
}int main() {//char *s = "mississippi";//char *p = "issip";char *s = "mississippi";char *p = "issip";printf("answer is %drn", strStr(s, p));
}

Python Solution: github

#coding=utf-8'''url: leetcode/problems/implement-strstr/@author:     zxwtry@email:      zxwtry@qq@date:       2017年4月1日@details:    Solution: 62ms 32.59%
'''class Solution(object):def getNext(self, p, pn):#return short pif pn < 2: return [-1]bi, fi, ne = 0, 2, [0] * pnne[0], ne[1] = -1, 0while fi < pn:if p[fi - 1] == p[bi]:bi += 1ne[fi] = bifi += 1elif bi <= 0:ne[fi] = 0fi += 1else:bi = ne[bi]return nedef strStr(self, s, p):""":type s: str origin string:type p: str pattern string:rtype: int"""sn = 0 if s == None else len(s)pn = 0 if p == None else len(p)#pn == 0 match s at index 0if pn == 0: return 0#sn == 0 and pn > 0 can not matchif sn == 0: return -1si, pi, ne = 0, 0, Next(p, pn)while si < sn:if s[si] == p[pi]:si += 1pi += 1if pi == pn: breakelif ne[pi] == -1:si += 1else:pi = ne[pi]return si - pn if pi == pn else -1if __name__ == "__main__":s, p ="mississippi", "issi"print(Solution().strStr(s, p))