admin管理员组文章数量:1636949
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://m.elefans.com/xitong/1729235644a1191955.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论