admin管理员组

文章数量:1636916

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

比较字符串，查找haystack中是否包含needle，如果包含则返回haystack中首先出现needle的指针，如果不包含则返回null

KMP算法，over[]代表覆盖度，从-1开始记，n代表 （n+1）个与模式串开头重复数

public class ImplementstrStr {
	public String strStr(String haystack, String needle) {
		if(haystack==null||needle==null||needle.length()>haystack.length())
			return null;
		if(needle.length()<1)
			return haystack;
		int[] over = new int[needle.length()];
		over[0]=-1;
		int preover;
		for(int i=1;i<needle.length();i++){
			preover = over[i-1];
			while(preover>=0&&needle.charAt(i)!=needle.charAt(preover+1)){
				preover = over[preover];
			}
			if(needle.charAt(i)==needle.charAt(preover+1))
				over[i]=preover+1;
			else 
				over[i]=-1;
		}
		int i=0,j=0;
		while(i<haystack.length()&&j<needle.length()){
			if(haystack.charAt(i)==needle.charAt(j)){
				i++;
				j++;
			}else if(j==0){
				i++;
			}else {
				j=over[j-1]+1;
			}
		}
		if(j==needle.length())
			return haystack.substring(i-j);
		return null;
	}
	public static void main(String[] args) {
		String haystack = "ababab135ab";
		String needle = "ab1";
		System.err.println(new ImplementstrStr().strStr(haystack, needle));
	}
}


本文标签： implementLeetCodeJavastrStr

版权声明：本文标题：[Leetcode] Implement strStr() (Java) 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://www.elefans.com/xitong/1729235644a1191955.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。