# Hdu - 1711. Number Sequence以及KMP算法总结
- KMP求解流程
- KMP next数组求解
- Hdu - 1711. Number Sequence模板题
***
#### [题目链接](http://acm.hdu.edu.cn/showproblem.php?pid=1711)
> http://acm.hdu.edu.cn/showproblem.php?pid=1711
#### 题目
就是求`str2`有没有在`str1`中出现，如果出现就返回第一个出现的位置。
### KMP求解流程
**这里先说明`next`数组的含义。**
- `next[i]`的含义是在`str[i]`之前的字符串`str[0...i]`中，必须以`str[i-1]`结尾的后缀子串(不能包含`str[0]`)与必须以`str[0]`开头的前缀子串(不能包含`str[i-1]`)的最大匹配长度；
- 这里我们先认为已经求得了匹配串的这个`next`数组(后面讲`next`数组求解)。
然后再看KMP求解流程:
- 当主串的指针`i1`和匹配串的指针`i2`所在位置`str1[i1] == str2[i2]`的时候，`i1++，i2++`；
- 否则，让`i2`直接跳到`i2`位置的next数组的值的位置，也就是`i2 = next[i2]`，这个过程相当于`str2`向右推动，看下图的两个失配的做法；
- 当然，如果`next[i2] = -1`了，说明`i2`到了`0`位置，开头都配不上，那`i1++`吧；
按照上面流程写出的代码:
```java
static int kmp(String s,String p){
if(s == null || p == null || p.length() < 1 || s.length() < p.length() )return -1;
char[] str1 = s.toCharArray();
char[] str2 = p.toCharArray();
int i1 = 0,i2 = 0; //甲乙
int[] next
