数据结构-KMP 算法（Knuth-Morris-Pratt 字符串查找算法）

1.什么是KMP算法：快速的从一个主串中找出一个你想要的子串

       KMP算法是一种改进的字符串匹配算法。KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。

首先，对于这个问题有一个很单纯的想法：从左到右一个个匹配，如果这个过程中有某个字符不匹配，比较指针就跳回去（比较指针回溯），将模式串向右移动一位。

/*** 暴力破解法* ts 主串* ps 模式串* 如果找到，返回在主串中第一个字符出现的下标，否则为-1*/
public static int bf(String ts, String ps) {int i = 0; // 主串的位置int j = 0; // 模式串的位置while (i < t.length && j < p.length) {if(t[i]==p[j]){//当两个字符相同，就比较下一个i++;j++;} else{i=i-j+1;// 一旦不匹配，i后退j=0;//j归0}}if(j==p.length){return i-j;} else{return -1;}
}

比较指针回溯使算法效率低，而KMP算法可以做到仅仅后移模式串，比较指针不回溯。

2.KMP算法实现过程

当某个字符不匹配时，我们观察发现箭头左边部分，上下字符串模式串和主串是完全匹配的。

模式串左右两端两个字串是完全匹配的，称为模式串的公共前后缀。

KMP核心：直接移动模式串，将公共前缀移动到公共后缀。

因为前后缀是匹配的，可以保证当前比较指针所在的位置左边的串上下匹配，且不会跳过某些匹配的情况。

注意：如果模式串存在多对公共前后缀，我们要取最长公共前后缀。

对于KMP算法只需研究模式串就可以。

3.KMP转化为代码形式（如何构建next数组）

首先把模式串放入数组中，模式串是从数组下标1开始的（根据个人喜好）。模式串的每一位都有可能与主串不匹配。

首先假设若1号位发生不匹配。

1号位与主串下一位比较。

若2号位发生不匹配。

 例题

1.剪花布条

一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？

输入格式

输入数据为多组数据，读取到 # 字符时结束。每组数据仅有一行，为由空格分开的花布条和小饰条。花布条和小饰条都是用可见 ASCII 字符表示的，不会超过  个字符。

注意：这个 # 应为单个字符。若某字符串开头有 #，不意味着读入结束！

输出格式

对于每组数据，输出一行一个整数，表示能从花纹布中剪出的最多小饰条个数。

样例

输入

abcde a3
aaaaaa aa
#

输出

0
3

数据范围与提示

对于全部数据，字符串长度<=1000 。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1005;
int n,m,next[maxn];
char s[maxn],t[maxn];//s[]为模式串，t[]为匹配串void getnext(){next[0]=0;for(int i=1;i<n;i++){int j=next[i-1];while(t[j]!=t[i]&&j>0){j=next[j-1];}if(t[j]==t[i]){next[i]=j+1;}else{next[i]=0;}}
} int kmp(){int j=0;int sum=0;for(int i=0;i<m;i++){while(t[j]!=s[i]&&j>0)j=next[j-1];if(t[j]==s[i]) {j++;}if(j>=n){sum++;j=0;}}return sum;
}int main(){while(~scanf("%s",s)){if(s[0]=='#'){break;}scanf("%s",t);m=strlen(s);n=strlen(t);getnext();printf("%d\n",kmp());}return 0;
} 

2.Power Strings

给定若干个长度  的字符串，询问每个字符串最多是由多少个相同的子字符串重复连接而成的。如：ababab 则最多有  个 ab 连接而成。

输入格式

输入若干行，每行有一个字符串。特别的，字符串可能为 . 即一个半角句号，此时输入结束。

样例

输入

abcd
aaaa
ababab
.

输出

1
4
3

数据范围与提示

字符串长度<=1e6 。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
char a[N];
int p[N],n;
void kmp()
{p[1]=0;int j=0;for(int i=1;i<n;i++){while(j>0&&a[j+1]!=a[i+1]){j=p[j];}if(a[j+1]==a[i+1]){j++;//如果已经相等，则看接下来的字符相不相等，若不相等则返回，说明还没有开始重复；否则接着匹配}p[i+1]=j;//开始时不相等，那么j不自增，继续看之后的串哪个i开始与j匹配}
}
int main()
{while(1){scanf("%s",a+1);if(a[1]=='.'){break;}n=strlen(a+1);kmp();if(n%(n-p[n])==0){printf("%d\n",n/(n-p[n]));} else{printf("%d\n",1);}}return 0;
}

3.Radio Transmission

给你一个字符串，它是由某个字符串不断自我连接形成的。但是这个字符串是不确定的，现在只想知道它的最短长度是多少。

输入格式

第一行给出字符串的长度 ，第二行给出一个字符串，全由小写字母组成。

输出格式

输出最短的长度。

样例

输入

8
cabcabca

输出

3

对于样例，我们可以利用 abc 不断自我连接得到 abcabcabc，读入的 cabcabca 是它的子串。

数据范围与提示

对于全部数据，1<=L<=1e6。

#include <bits/stdc++.h>
using namespace std;
char p[1000005];
int next[1000005],len;
void get_next()
{int i,j;next[0]=j=-1;i=0;while(i<len){while(j!=-1&&p[j]!=p[i]){j=next[j];}  next[++i]=++j;}
}int main()
{int n;cin>>n;scanf("%s",p);len=strlen(p);get_next();
//    for(int i=0;i<len;i++)
//    {
//        cout<<next[i]<<" ";
//    }cout<<n-next[n];return 0;
}