public class Solution {
public int strStr(String haystack, String needle) {
int[] next=new int[needle.length()];
generateNextArray(next,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 i-j;
return -1;
}
void generateNextArray(int[] next, String needle)
{
int k=-1;
if(next.length>0)
next[0]=-1;
int i=0;
while(i<needle.length()-1)
{
if(k==-1||needle.charAt(k)==needle.charAt(i))
{
k++;
i++;
next[i]=k;
}
else
k=next[k];
}
}
}
http://blog.csdn.net/v_july_v/article/details/7041827
转载于:https://www.cnblogs.com/asuran/p/7580062.html
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
