这是一道模板题，给定一个字符串A和一个字符串B，求B在A中的出现次数。A和B中的字符均为英语大写字母或者小写字母。A中不同位置出现的B可重叠。

输入格式：

输入共两行，分别是字符串A和字符串B

输出格式：

输出一个整数，表示B在A中的出现次数。

样例：

输入：

zyzyzyz

zyz

输出：

3

此处参考文档为：字符串匹配的KMP算法 - 阮一峰的网络日志 (ruanyifeng.com)​​​​​​

看了好多篇的介绍，认为这篇讲的最清楚，放入此文供大家参考。

内容如下：

有一个字符串"BBC ABCDAB ABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最常用的之一。这个算法完成该任务不需要主串回溯，它以三个发明者命名，起头的那个K就是著名科学家Donald Knuth。

下面以该例子讲解KMP算法的具体过程。

1）

首先，字符串"BBC ABCDAB ABCDABCDABDE"的第一个字符与搜索词"ABCDABD"的第一个字符，进行比较。因为B与A不匹配，所以搜索词后移一位。 

2）

因为B与A不匹配，搜索词再往后移。

3） 

 就这样，直到字符串有一个字符，与搜索词的第一个字符相同为止。

4）

 接着比较字符串和搜索词的下一个字符，还是相同。

5）

直到字符串有一个字符，与搜索词对应的字符不相同为止。

6）

这时，最自然的反应是，将搜索词整个后移一位，再从头逐个比较。这样做虽然可行，但是效率很差，因为你要把"搜索位置"移到已经比较过的位置，重比一遍。

7）

一个基本事实是，当空格与D不匹配时，你其实知道前面六个字符是"ABCDAB"。KMP算法的想法是，设法利用这个已知信息，不要把"搜索位置"移回已经比较过的位置，继续把它向后移，这样就提高了效率。

8）

怎么做到这一点呢？可以针对搜索词，算出一张《部分匹配表》（Partial Match Table）。这张表是如何产生的，后面再介绍，这里只要会用就可以了。

9）

已知空格与D不匹配时，前面六个字符"ABCDAB"是匹配的。查表可知，最后一个匹配字符B对应的"部分匹配值"为2，因此按照下面的公式算出向后移动的位数：

　　移动位数 = 已匹配的字符数 - 对应的部分匹配值

因为 6 - 2 等于4，所以将搜索词向后移动4位。

10）

因为空格与Ｃ不匹配，搜索词还要继续往后移。这时，已匹配的字符数为2（"AB"），对应的"部分匹配值"为0。所以，移动位数 = 2 - 0，结果为 2，于是将搜索词向后移2位。

11）

因为空格与A不匹配，继续后移一位。

12）

 逐位比较，直到发现C与D不匹配。于是，移动位数 = 6 - 2，继续将搜索词向后移动4位。

 13）

逐位比较，直到搜索词的最后一位，发现完全匹配，于是搜索完成。如果还要继续搜索（即找出全部匹配），移动位数 = 7 - 0，再将搜索词向后移动7位，这里就不再重复了。

14）

下面介绍《部分匹配表》是如何产生的。

首先，要了解两个概念："前缀"和"后缀"。 "前缀"指除了最后一个字符以外，一个字符串的全部头部组合；"后缀"指除了第一个字符以外，一个字符串的全部尾部组合。

15）

"部分匹配值"就是"前缀"和"后缀"的最长的共有元素的长度。以"ABCDABD"为例，

　　－　"A"的前缀和后缀都为空集，共有元素的长度为0；

　　－　"AB"的前缀为[A]，后缀为[B]，共有元素的长度为0；

　　－　"ABC"的前缀为[A, AB]，后缀为[BC, C]，共有元素的长度0；

　　－　"ABCD"的前缀为[A, AB, ABC]，后缀为[BCD, CD, D]，共有元素的长度为0；

　　－　"ABCDA"的前缀为[A, AB, ABC, ABCD]，后缀为[BCDA, CDA, DA, A]，共有元素为"A"，长度为1；

　　－　"ABCDAB"的前缀为[A, AB, ABC, ABCD, ABCDA]，后缀为[BCDAB, CDAB, DAB, AB, B]，共有元素为"AB"，长度为2；

　　－　"ABCDABD"的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB]，后缀为[BCDABD, CDABD, DABD, ABD, BD, D]，共有元素的长度为0。

 16）

"部分匹配"的实质是，有时候，字符串头部和尾部会有重复。比如，"ABCDAB"之中有两个"AB"，那么它的"部分匹配值"就是2（"AB"的长度）。搜索词移动的时候，第一个"AB"向后移动4位（字符串长度-部分匹配值），就可以来到第二个"AB"的位置。 

1）算法描述。有两种求解方法，分别是根据前一个字符的next值求以及根据前一个字符的next值求。本文只介绍第一种。

字符串记作 p；next 数组记作 next；

约定：

下标从 1 开始算，注意，不是从 0 开始算 字符串长度 >2 1）第一个字母的 next 值置 0 （next[1] = 0），第二个字母的 next 值置 1（next[2] = 1） ； 2）从第 3 个开始，计算第 i 个位置的 next 值时，检查

p[i-1]== p[next[i-1]] ?（即这两个值是否相等）

解释：第 i 个位置的前一个位置的值（即 p[i-1]，记作 m）与以 m 的 next 值（即 next[i-1]）为下标的值（即 p[next[i-1]]，记作 n）是否相等，（看的懵懵的也没关系，后面会有例子）

若相等，则 next[i] = next[i-1] + 1 若不等，则继续往回找，检查

p[i-1]== p[next[next[i-1]]] ?

若相等，则 next[i] = next[next[i-1]] + 1 若不等，则继续往回找，直到找到下标为 1 还不等（即字符串第一个元素），直接赋值 next[i] = 1

2）举个例子方便理解上述算法的流程。

求解： （1）对应上面第一种求法 1）初始化

2）求下标为 3 的字符的 next 值 P[3-1] = P[2] = ‘b’; next[3-1] = next[2] = 1 ; P[next[3-1]] = P[1] = ‘a’; P[3-1] != P[next[3-1]] ，但是此时已经回溯到了第一个元素， ∴ 直接P[3] = 1 ;

3）求下标为 4 的字符的 next 值 P[4-1] = P[3] = ‘a’; next[4-1] = next[3] = 1 ; P[next[4-1]] = P[1] = ‘a’; P[4-1] == P[next[4-1]] ; ∴ next[4] = next[4-1] + 1 = 2 ;

4）求下标为 5 的字符的 next 值 P[5-1] = P[4] = ‘b’; next[5-1] = next[4] = 2 ; P[next[5-1]] = P[2] = ‘b’; P[5-1] == P[next[5-1]] ; ∴ next[5] = next[5-1] + 1 = 3 ;

5）求下标为 6 的字符的 next 值 推导过程同上 => next[6] = next[6-1] + 1 = 4 ;

6）求下标为 7 的字符的 next 值 P[7-1] = P[6] = ‘a’; next[7-1] = next[6] = 4 ; P[next[7-1]] = P[4] = ‘b’; P[7-1] != P[next[7-1]] && 此时还未回到第一个，继续 next[next[7-1]] = next[4] = 2 ; P[next[next[7-1]]] = P[2] = ‘b’;番外（1） P[7-1] != P[next[next[7-1]]] && 但是此时还未回到第一个，继续 next[next[next[7-1]]] = next[2] = 1 ; P[next[next[next[7-1]]]] = P[1] = ‘a’ ; P[7-1] == P[next[next[next[7-1]]]] ; ∴ next[7-1] = next[next[next[7-1]]] + 1 = next[2] + 1 = 2 ;

7）求下标为 8 的字符的 next 值 P[8-1] = P[7] = ‘a’； next[8-1] = next[7] = 2 ; P[next[8-1]] = P[2] = ‘b’; P[8-1] != P[next[8-1]] ,但是还没回到第一个元素，继续 next[next[8-1]] = next[2] = 1 ; P[next[next[8-1]]] = P[1] = ‘a’; P[8-1] == P[next[next[8-1]]]; ∴ next[8] = next[next[8-1]] + 1 = 2

8）求下标为 9 的字符的 next 值 推导过程同4) => next[9] = next[9-1] + 1 = 3 ;

9）求下标为 10 的字符的 next 值 推导过程同4) => next[10] = next[10-1] + 1 = 4 ;

10）求下标为 11 的字符的 next 值 推导过程同4) => next[11] = next[11-1] + 1 = 5 ;

11）求下标为 12 的字符的 next 值

推导过程同4) => next[12] = next[12-1] + 1 = 6 ;

3）算法实现。