实现strstr函数

[编程题]实现strstr函数

热度指数：11650 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

实现函数 strStr。

函数声明如下：

char *strStr(char *str, char *dest)

返回一个指针，指向dest第一次在str中出现的位置，如果dest不是str的子串，则返回null

算法知识视频讲解

查看答案及解析

Java

cooking969

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;
    }
}

发表于 2021-10-02 10:03:16 回复(0)

Java

华科平凡

Java Solution

public class Solution {
    public String strStr(String haystack, String needle) {
        int index = haystack.indexOf(needle);
        if(index>-1)
            return haystack.substring(index);
        return null;
    }
}

发表于 2018-07-04 10:49:02 回复(0)

Java

Holiday_12138

//KMP这算法虽然知道原理，每次都忘怎么具体实现。。
public class Solution {
    public String strStr(String haystack, String needle) {
        if(needle.length() < 1)
            return haystack;
        if(haystack.length() < 1)
            return null;
        int[] nextval = getNext(needle.toCharArray());
        int i = 0;
        int j = 0;
        while(i < haystack.length() && j < needle.length()) {
            if(j < 0 || haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
                
            }
            else {
                j = nextval[j];
            }
        }
        if(j == needle.length())
        	return haystack.substring(i-j);
        else
            return null;
    }
    
    public int[] getNext(char[] ch) {
        int n = ch.length;
        int i = 0, j = -1;
        int[] nextval = new int[n];
        nextval[0] = -1;
        while(i < n-1) {
            if(j == -1 || ch[i] == ch[j]) {
                i++;
                j++;
                if(ch[i] != ch[j]) {
                    nextval[i] = j;
                }
                else
                    nextval[i] = nextval[j];
            }
            else
                j = nextval[j];
        }
        return nextval;
    }
}

发表于 2017-06-04 13:46:38 回复(0)

Java

城市里的养猫者

public int strStr(String haystack, String needle) {
  
  for (int i = 0; ; i++) {
    
    for (int j = 0; ; j++) {
      
      if (j == needle.length()) return i;
      
      if (i + j == haystack.length()) return -1;
      
      if (needle.charAt(j) != haystack.charAt(i + j)) break;
    }
  }
}
    }
  }
}

发表于 2017-03-12 23:19:31 回复(0)

Java

詆調壹點

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;
	}
}

发表于 2016-11-04 22:17:16 回复(0)