实现函数 strStr。
函数声明如下:
char *strStr(char *str, char *dest)
返回一个指针,指向dest第一次在str中出现的位置,如果dest不是str的子串,则返回null
//KMP算法 public class Solution { public int[] getNext(String needle ){ int j=-1; int i=0; int[] next = new int[needle.length()]; next[i]=j; while(i<needle.length()-1){ if (j==-1||needle.charAt(i)==needle.charAt(j)){ i++; j++; if(needle.charAt(i)!=needle.charAt(j)){ next[i]=j; }else{ next[i]=next[j]; } }else{ j=next[j]; } } return next; } public String strStr(String haystack, String needle) { if(haystack==null||needle==null||needle.length()==0){ return haystack; } if(needle.length()>haystack.length()){ return null; } int[] next = getNext(needle); int i=0; int j=0; while(i<haystack.length()&&j<needle.length()){ if(j==-1||haystack.charAt(i)==needle.charAt(j)){ i++; j++; }else{ j=next[j]; } } if(j>=needle.length()){ return haystack.substring(i-needle.length()); }else{ return null; } } }
public class Solution { public String strStr(String haystack, String needle) { if(haystack==null || needle == null || needle.length()==0) return haystack; if(needle.length()>haystack.length()) return null; char[] a = haystack.toCharArray(); char[] b = needle.toCharArray(); int[] next = getNextArray(b); int i = 0,j = 0; while (i < a.length) { while (j >= 0 && a[i] != b[j]) { j = next[j]; } i++; j++; if (j == b.length) { return haystack.substring(i - b.length); } } return null; } private int[] getNextArray(char[] s){ if(s.length==1) return new int[]{-1}; int[] next = new int[s.length]; next[0] = -1; next[1] = 0; int pos = 2; int cn = 0; while(pos<next.length){ if(s[pos-1]==s[cn]) next[pos++] = ++cn; else if(cn>0) cn = next[cn]; else next[pos++] = 0; } return next; } }
char *strStr(char *haystack, char *needle) { if (*needle == '\0') return haystack; // 若needle为空,返回haystack if (*haystack == '\0') return NULL; // 否则,若haystack为空,则返回NULL while (*haystack != '\0') { // 从haystack的每一个位置开始查找,是否有和needle相同的字符串 char *p = haystack, *q = needle; while (*p != '\0' && *q != '\0' && *p == *q) {p ++; q ++;} // 逐个比对是否相同 if (*q == '\0') return haystack; // 若有,则直接返回当前haystack的位置 haystack ++; // 否则继续后移 } return NULL; }
public class Solution { public String strStr(String haystack, String needle) { if (haystack == null || needle == null || haystack.length() < needle.length()) return null; if (needle.length() == 0) return haystack.substring(0); for (int i = 0; i <= haystack.length() - needle.length(); i++) { for (int j = 0; j < needle.length(); j++) { if (haystack.substring(i, i + needle.length()).equals(needle)) return haystack.substring(i); } } return null; } }
class Solution { public: char *strStr(char *haystack, char *needle) { int m = strlen(haystack); int n = strlen(needle); if(m < n) return NULL; int d = m - n; for(int i=0;i<=d;i++) { int j = 0; for(;j<n;j++) { if(haystack[i+j] != needle[j]) break; } if(j == n) return haystack + i; } return NULL; } };
//Sunday算法 char *strStr(char *haystack, char *needle) { int len1=strlen(haystack),len2=strlen(needle); if(len2==0) return haystack; if(len2>len1) return NULL; //用map保存needle中每个字符从后往前第一次出现的位置 unordered_map<char,int> pos; for(int i=len2-1;i>=0;--i){ if(pos.find(needle[i])==pos.end()) pos[needle[i]]=i; } int i=0,j=0; while(i<len1&&j<len2){ if(haystack[i]==needle[j]){ ++i; ++j; }else{ int index=pos[haystack[i+len2-j]]; i=i+len2-j-index; j=0; } if(j==len2) return &haystack[i-len2]; } return NULL; }
public class Solution { public static String strStr(String haystack, String needle) { if(haystack == null || needle == null || needle.length() == 0) return haystack; if(needle.length() > haystack.length()) return null; for (int i = 0; i < haystack.length(); i ++ ) { if(haystack.charAt(i) == needle.charAt(0) && i + needle.length() <= haystack.length() && haystack.substring(i, i + needle.length()).equals(needle)) { return haystack.substring(i); } } return null; } }
public class Solution { public String strStr(String haystack, String needle) { int lengthOfStack = haystack.length(); int lengthOfNeedle = needle.length(); if(haystack == null || needle == null ||lengthOfStack < lengthOfNeedle ){ return null; } for(int i=0; i<=(lengthOfStack - lengthOfNeedle);i++){ if(haystack.substring(i, i+lengthOfNeedle).equals(needle)){ return haystack.substring(i); } } return null; } }
class Solution { public: vector<int> getNext(char* ms){ int l=strlen(ms); vector<int> next(l); if(l==1){ next[0]=-1; return next; } next[0]=-1; next[1]=0; int pos=2; int cn=0; while(pos<next.size()){ if(ms[pos-1]==ms[cn]) next[pos++]=++cn; else if(cn>0) cn=next[cn]; else next[pos++]=0; } return next; } char *strStr(char *haystack, char *needle) { int l1=strlen(haystack),l2=strlen(needle); if(l1<l2) return NULL; if(l1==0||l2==0) return haystack; int si=0,mi=0; vector<int> next=getNext(needle); while(si<l1&&mi<l2){ if(haystack[si]==needle[mi]){ si++; mi++; }else if(next[mi]==-1){ si++; }else{ mi=next[mi]; } } return mi==l2 ? &haystack[si-mi] : NULL; } };
// 这样看起来简单理解一点? char *strStr(char *haystack, char *needle) { int m = strlen(haystack),n = strlen(needle); if(m<n) return nullptr; int diff = m-n+1; for(int start=0;start<diff;start++) { int j=0; for(;j<n;j++) { if(haystack[start+j] != needle[j]) break; } if(j==n) { return haystack+start; } } return nullptr; }
class Solution { public: char *strStr(char *str, char *dest) { const char* r1 = str; const char* r2 = dest; while (*r2!='\0'&&*r1!='\0') { if (*r1 == *r2) { r1++, r2++;} else { r1 =++str; r2 = dest; } } if (*r2 == 0) return str; else return NULL; } };
public class Solution { public String strStr(String str, String dest) { char[] t = str.toCharArray(); char[] p = dest.toCharArray(); if (p.length == 0) { return str; } int i = 0, j = 0; int[] next = getNext(dest); while (i < t.length && j < p.length) { if (j == -1 || t[i] == p[j]) { i++; j++; } else { j = next[j]; } } if (j == p.length) { return str.substring(i - j); } return null; } public static int[] getNext(String ps) { char[] p = ps.toCharArray(); int[] next = new int[p.length]; int j = 0; int k = -1; next[0] = -1; while (j < p.length - 1) { if (k == -1 || p[k] == p[j]) { if (p[++k] == p[++j]) { next[j] = next[k]; } else { next[j] = k; } } else { k = next[k]; } } return next; } }
KMP算法,关键在于求next数组,求next数组搞了好久都没搞懂,干脆记住算了。。。吧
// // Created by jt on 2020/8/14. // #include <string> using namespace std; class Solution { public: char *strStr(char *haystack, char *needle) { int size1 = strlen(haystack), size2 = strlen(needle); if (size2 == 0) return haystack; int next[size2], i = 0, j = 0; getNext(needle, next, size2); while(i < size1 && j < size2) { if (j == -1 || haystack[i] == needle[j]) { ++i; ++j; } else { j = next[j]; } } if (j == size2) return haystack + i - j; else return nullptr; } void getNext(char *a, int *next, int size) { int i = 0, j = -1; // i指向尾子串尾部,j指向头子串尾部 next[0] = -1; while (i < size) { if (j == -1 || a[i] == a[j]) { if (a[++i] == a[++j]) next[i] = next[j]; else next[i] = j; } else j = next[j]; } } };
char *strStr(char *haystack, char *needle) { char* res = nullptr; //正确的: if(*needle =='\0') return haystack; if(*haystack == '\0') return nullptr; //错误的: if(*haystack == '\0') return nullptr; if(*needle =='\0') return haystack; } //为什么???
class Solution { public: void inital(int* &findnext,char *needle,int n){ findnext[0]=-1; for(int i=1;i<n;i++){/*第i个位子匹配不成功*/ int off = 1; //措off个位子匹配 while(off<=i){ if(needle[i]==needle[i-off]) off++; else{ int j; for(j=0;j<i-off;j++){ if(needle[j]!=needle[j+off]){ off++; break; } } if(j==i-off){ findnext[i]=i-off; break; } } } if(off==i+1) findnext[i]=-1; } } char *strStr(char *haystack, char *needle) { int sublen = 0; int len=0; int i=0; while(needle[i]!='\0'){ sublen++; i++; } i=0; while(haystack[i]!=0){ len++; i++; } if(sublen==0 && len==0) return haystack; if(sublen!=0&&len==0) return NULL; if(sublen==0 && len!=0) return haystack; int *findnext=new int[sublen]; inital(findnext,needle,sublen); int j=0; i=0; while(haystack[j]!='\0'){ if(haystack[j]==needle[i]){ if(i==sublen-1){ return haystack+j-sublen+1; } j++; i++; }else{ i=findnext[i]; if(i==-1){ i=0; j++; } } } return NULL; } };
public class Solution { /** * leetcode: implement-strstr * 虽然读不懂题目,但是看了讨论是要求包含needle子串的起点,返回haystack从这个起点开始的所有字符串 * 例如 haystack = "abcdefg", needle = "cd", 返回cdefg * 1.首先想到的是最简单的做法,遍历haystack,每走一位就匹配一次needle,看是否全部包含 * 这种方法最坏情况下时间复杂度O((n-m+1)*m),平均时间复杂度O(n+m) ps:我自己不会算,参考https://blog.csdn.net/ylyg050518/article/details/78825387 * 2.kmp算法. * 具体思想就是根据匹配串needle求一个next数组,表示如果当前字母不匹配,跳转到哪里开始匹配,而不是每次都从头开始匹配 * 例如haystack = "abcdababef", needle = "ababe", 假设i是needle的指针,当i=4(needle.charAt(i) == 'e')不匹配时,应该把i置为2而不是0 * 当i=4时才匹配失败,说明'abab'一定匹配通过,因此下次没必要从头开始匹配,而可以从i=2开始匹配,因为'abab'相同的最长前缀后缀为'ab'. * 这里可能有点难理解,因为这就是kmp的核心,'abab'的所有前缀为[a, ab, aba], 所有后缀为[b, ab, bab],所以相同的最长前缀后缀为'ab' * 因此当'e'匹配失败时,表示后缀ab一定能够匹配通过,所以前缀ab也一定能匹配通过,这时就不需要再回溯回去再匹配一次前缀,直接从前缀ab后面开始匹配就行 * 具体的实现可以网上搜索,https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html 这篇文章讲的很不错而且有图说明 */ public String strStr(String haystack, String needle) { if (needle.length() == 0) return haystack; int[] next = next(needle); int a = 0, b = 0; while (a < haystack.length()) { if (haystack.charAt(a) == needle.charAt(b)) { a ++; b ++; } else { if (next[b] >= 0) { b = next[b]; } else { a ++; b = 0; } } if (b == needle.length()) { break; } } if (b == needle.length()) { return haystack.substring(a - b); } return null; } /** * 动态规划求出next数组 */ private static int[] next(String p) { int[] r = new int[p.length()]; // 求出到每个字符的最长相同前缀后缀的长度 for (int i = 1 ; i < p.length() ; i ++) { if (r[i - 1] == 0) { r[i] = p.charAt(i) == p.charAt(0) ? 1 : 0; } else { if (p.charAt(i) == p.charAt(r[i - 1])) { r[i] = r[i - 1] + 1; } else { r[i] = p.charAt(i) == p.charAt(0) ? 1 : 0; } } } // 整体右移,因为next数组表示的是当这个字符匹配失败该跳到哪里去,确切来说,当前字符只关心前一个字符的最长相同前缀后缀的长度 for (int i = r.length - 1 ; i > 0 ; i --) { r[i] = r[i - 1]; } r[0] = -1; return r; } }