s2是模式串,s1和s2下标均从1开始
//获得next[]数组
static void getNext() {
Arrays.fill(next,-1);
next[1]=0;
int i=1,j=0;
while (i<=n) {
if (j==0||s2[i]==s2[j])
next[++i]=++j;
else j=next[j];
}
}
//模式匹配,其中s2是模式串(子串)
static int kmp() {
getNext();
int i=1,j=1;
while (i<=l) {
if (j==0||s1[i]==s2[j]) {
i++;
j++;
}
else j=next[j];
if (j==n+1)
return i-n;
}
return -1;
}



