蓝桥杯算法竞赛专题优质解析：KMP算法（搜索匹配优化）
1.情境引入
KMP本身不复杂，但网上绝大部分的文章较混乱。下面，从暴力匹配算法讲起，随后阐述KMP的流程 步骤

next 数组的简单求解

递推原理

代码求解

接着基于next 数组匹配

谈到有限状态自动机

next 数组的优化

KMP的时间复杂度分析，

最后简要介绍两个KMP的扩展算法。

给大家一个清晰的KMP，希望更多的人不再被KMP折磨或纠缠。有何疑问，欢迎随时留言评论，thanks。



2. 暴力匹配算法
假设现在我们面临这样一个问题：有一个文本串S，和一个模式串P，现在要查找P在S中的位置，怎么查找呢？
如果用暴力匹配的思路，并假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置，则有：


[1 ] 如果当前字符匹配成功（即S[i] == P[j]），则i++，j++，继续匹配下一个字符；


[ 2] 如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0。相当于每次匹配失败时，i 回溯，j 被置为0。


int baoli(string s,string p) 
{
	int sLen = strlen(s);
	int pLen = strlen(p);
	int i = 0;
	int j = 0;
	while (i < sLen && j < pLen) {
		if (s[i] == p[j]) { //①如果当前字符匹配成功（即S[i] == P[j]），则i++，j++
			i++;
			j++;
		} else { //②如果错误（即S[i]! = P[j]），令i = i - (j - 1)，j = 0
			i = i - j + 1;
			j = 0;
		}
	}
	//匹配成功，返回模式串p在文本串s中的位置，否则返回-1
	if (j == pLen)
		return i - j;
	else
		return -1;
}
}


举个例子，如果给定文本串S“BBC ABCDAB ABCDABCDABDE”，和模式串P“ABCDABD”，现在要拿模式串P去跟文本串S匹配，整个过程如下所示：


S[0]为B，P[0]为A，不匹配，执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[1]跟P[0]匹配，相当于模式串要往右移动一位（i=1，j=0）




S[1]跟P[0]还是不匹配，继续执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，S[2]跟P[0]匹配（i=2，j=0），从而模式串不断的向右移动一位（不断的执行“令i = i - (j - 1)，j = 0”，i从2变到4，j一直为0）




直到S[4]跟P[0]匹配成功（i=4，j=0），此时按照上面的暴力匹配算法的思路，转而执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，可得S[i]为S[5]，P[j]为P[1]，即接下来S[5]跟P[1]匹配（i=5，j=1）



S[5]跟P[1]匹配成功，继续执行第①条指令：“如果当前字符匹配成功（即S[i] == P[j]），则i++，j++”，得到S[6]跟P[2]匹配（i=6，j=2），如此进行下去



直到S[10]为空格字符，P[6]为字符D（i=10，j=6），因为不匹配，重新执行第②条指令：“如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0”，相当于S[5]跟P[0]匹配（i=5，j=0）



至此，我们可以看到，如果按照暴力匹配算法的思路，尽管之前文本串和模式串已经分别匹配到了S[9]、P[5]，但因为S[10]跟P[6]不匹配，所以文本串回溯到S[5]，模式串回溯到P[0]，从而让S[5]跟P[0]匹配。


而S[5]肯定跟P[0]失配。为什么呢？因为在之前第4步匹配中，我们已经得知S[5] = P[1] = B，而P[0] = A，即P[1] != P[0]，故S[5]必定不等于P[0]，所以回溯过去必然会导致失配。那有没有一种算法，让i 不往回退，只需要移动j 即可呢？
答案是肯定的。这种算法就是本文的主旨KMP算法，它利用之前已经部分匹配这个有效信息，保持i 不回溯，通过修改j 的位置，让模式串尽量地移动到有效的位置。

题解：
#include<bits/stdc++.h>
using namespace std;
int baoli(string s,string p) 
{
	int sLen = s.size();
	int pLen = p.size();
	int i = 0,j =0 ;

	while (i < sLen && j < pLen) {
		if (s[i] == p[j]) { 
			i++;
			j++;
		} else { 
			i = i - j + 1;
			j = 0;
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}

int main()
{
	string s="BBC ABCDAB ABCDABCDABDE",p="ABCDABD";
	cout<<baoli(s,p); 
	return 0;
}


3.KMP算法
3.1入门
下面先直接给出KMP的算法流程（如果感到一点点不适，没关系，坚持下，稍后会有具体步骤及解释，越往后看越会柳暗明）：


假设现在文本串S匹配到 i 位置，模式串P匹配到 j 位置


如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++，继续匹配下一个字符；


如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j]。此举意味着失配时，模式串P相对于文本串S向右移- 动了j - next [j] 位。



换言之，当匹配失败时，模式串向右移动的位数为：失配字符所在位置 - 失配字符对应的next 值（next 数组的求解会在下文的

3.3.3节中详细阐述），即移动的实际位数为：j - next[j]，且此值大于等于1

在某个字符失配时，该字符对应的next 值会告诉你下一步匹配中，模式串应该跳到哪个位置（跳到next [j] 的位置）。如果next [j] 等于0或-1，则跳到模式串的开头字符，若next [j] = k 且 k > 0，代表下次匹配跳到j 之前的某个字符，而不是跳到开头，且具体跳过了k 个字符

KMP算法

int Kmp(string s,string p)
{
	int i = 0,j = 0;
	int sLen = s.size();
	int pLen = p.size();
	while (i < sLen && j < pLen) {
		if (j == -1 || s[i] == p[j]) {
			i++;
			j++;
		} else {
			j = next[j];
		}
	}
	if (j == pLen)
		return i - j;
	else
		return -1;
}

3.2next[]求法
void GetNext(string p,int next[])
{
	int pLen = p.size();
	next[0] = -1;
	int k = -1;
	int j = 0;
	while (j < pLen - 1)
	{
		//p[k]表示前缀，p[j]表示后缀
		if (k == -1 || p[j] == p[k]) 
		{
			++k;
			++j;
			next[j] = k;
		}
		else 
		{
			k = next[k];
		}
	}
}


逐步优化中！

蓝桥杯算法竞赛专题优质解析：二分法、三分法
.

尊重原创 转载注明 

.

如有建议，请联系：（1）QQ 群，849225619；（2）作者QQ，78983438

#------------------------------------------------------------
#作者：新零云

#时间：2020-3-18日初稿（日后会维护内容）
#------------------------------------------------------------
_________________________________全局概览_________________________________
蓝桥杯算法竞赛专题优质解析：二分法、三分法
1.1整数二分模板 - 普通
1.2整数二分模板 - STL -	lower_bound()
2.1简单例题
2.2进阶例题 - 最小值最大化（最小值尽量大）
3.1实数二分模板
3.2实数二分例题
4.二分法精选例题
5.1三分法模板

1.1整数二分模板 - 普通
在有序数列a[]中查找某个数x；如果数列中没有x，找它的后继。


int sec(int a[],int n,int x)
{
	int left=0,right=n;   //这里是n  非n-1
	while(left<right)
	{
		int mid=(right-left)/2+left;
		if(a[mid]>=x) right=mid;
		else left=mid+1;
	}
	return left;	
} 

.
1.2整数二分模板 - STL -	lower_bound()
#include <bits/stdc++.h>
using namespace std;
int a[8]={1,2,3,5,6,7,9,10};
int main()
{
	cout<<lower_bound(a,a+8,7)-a;
	return 0;
}

.

2.1简单例题
∎问题描述：

输入n ( n≤100,000)个整数，找出其中的两个数，它们之和等于整数m(假定肯定有解)。题中所有整数都能用int 表示。
#include <bits/stdc++.h>
using namespace std;
int a[100010];
void sec(int a[],int n,int m)    //二分思想 核心
{
	int left=0,right=n-1;
	while(left<right)
	{
		int sum=a[left]+a[right];
		if(sum>m) right--;
		if(sum<m) left++;
		if(sum==m) 
		{
			cout<<a[left]<<"+"<<a[right]<<"="<<m<<endl;
			left++;
		}
	}
}
int main()
{
	for(int i=1;i<=100000;i++) a[i]=i;
	sec(a,100000,1587);
	return 0;
}


.

二分法的典型应用有：最小化最大值、最大化最小值。
2.2进阶例题 - 最小值最大化（最小值尽量大）
∎问题描述：“进击的奶牛” - 洛谷

在一条很长的直线上，指定n个坐标点（x1, …, xn）。有c头牛，安排每头牛站在其中一个点（牛棚）上。这些牛喜欢打架，所以尽量距离远一些。问最近的两头牛之间距离的最大值可以是多少。

这个题目里，所有的牛棚两两之间的距离有个最小值，题目要求使得这个最小值最大化。

.

∎题解

二分思想：分析从小到大检查dis的过程，发现可以用二分的方法找这个dis。这个dis符合二分法：它有上下边界、它是单调递增的。
.

不知道为啥有三个测试点没通过
#include <bits/stdc++.h>
using namespace std;
int n,c,x[10005]; //牛棚数量，牛数量，牛棚坐标

bool check(int dis)  //当牛之间距离为dis时，检查牛棚够不够
{
	int cn=1,place=0;
	for(int i=1;i<n;i++)
	{
		if(x[i]-x[place]>=dis)
		{
			cn++;
			place=i;
		}
	}
	if(cn>=c) return true;
	else return false;
}

int main()
{
	scanf("%d%d",&n, &c);
	for(int i=0;i<n;i++)   scanf("%d",&x[i]);
	sort(x,x+n);
	int l=0,r=x[n-1]-x[0];
	int ans=0;
	while(l<r)
	{
		int mid=(r-l)/2+l;
		if(check(mid))  //当牛之间距离最小为mid时，牛棚够不够?
		{
			ans=mid;  //牛棚够，先记录mid
			l=mid+1;   //扩大距离
		}
		else r=mid;  //牛棚不够，缩小距离
	}
	cout<<ans;
	return 0;
}



.
3.1实数二分模板
const double eps =1e-7;        //精度
while(right - left > eps){   
      double mid = left+(right-left)/2;
      if (条件) right=mid;  //判定，然后继续二分
      else  left  = mid;
}

.
3.2实数二分例题
∎题目描述

主人过生日，m个人来庆生，有n块半径不同的圆形蛋糕，由m+1个人（加上主人）分，每人的蛋糕必须一样重，而且是一整块（不能是几个蛋糕碎块，也就是说，每个人的蛋糕都是从一块圆蛋糕中切下来的完整一块）。问每个人能分到的最大蛋糕是多大。

∎题解

最小值最大化问题。设每人能分到的蛋糕大小是x，用二分法枚举x。
自己有点晕
#include <bits/stdc++.h>
using namespace std;
double PI=acos(-1.0);  //3.141592653589793;
const double eps=1e-7;
double area[10010];
int n,m;
bool check(double mid)
{
	int sum=0;
	for(int i=0;i<n;i++)
	{
		sum+=(int)(area[i]/mid);   //把每个圆蛋糕都按大小mid分开。统计总数
	}
	if(sum>=m) return true;
	else return false;
}
int main()
{
	int t;
	cin>>t;
	while(t--)
	{
		cin>>n>>m;
		m++;
		double maxx=0;
		for(int i=0;i<n;i++)
		{
			int r; cin>>r;
			area[i]=r*r*PI;
			if(maxx<area[i])	maxx=area[i];  //最大的一块蛋糕
		}	
		double l=0,r=maxx;
		while(r-l>eps)
		{
			double mid=(r-l)/2+l;
			if(check(mid)) l=mid;
			else r=mid;
		}
		cout<<l<<endl;
	} 
	return 0;
}



.
4.二分法精选例题
饥饿的奶牛　　https://www.luogu.org/problem/P1868

寻找段落　　　https://www.luogu.org/problem/P1419

小车问题　　　https://www.luogu.org/problem/P1258

借教室　　　　https://www.luogu.org/problem/P1083

跳石头　　　　https://www.luogu.org/problem/P2678

聪明的质监员　https://www.luogu.org/problem/P1314

分梨子　　　　https://www.luogu.org/problem/P1493

第 k大　　　　   http://acm.hdu.edu.cn/showproblem.php?pid=6231

.
5.1三分法模板
今天有点累，过几天在更新！

试题A:组队


 问题描述：

作为篮球队教练，你需要从以下名单中选出 1 号位至 5 号位各一名球员， 组成球队的首发阵容。

每位球员担任 1 号位至 5 号位时的评分如下表所示。请你计算首发阵容 1 号位至 5 号位的评分之和最大可能是多少？


 

试题B:不同子串


问题描述：

一个字符串的非空子串是指字符串中长度至少为 1 的连续的一段字符组成 的串。例如，字符串aaab 有非空子串a, b, aa, ab, aaa, aab, aaab，一共 7 个。 注意在计算时，只算本质不同的串的个数。 请问，字符串0100110001010001 有多少个不同的非空子串？


import java.util.ArrayList;

public class Main {
	public static void main(String[] args) {
		ArrayList<String> list = new ArrayList<>();
        //首先使用题目给定的条件进行测试
//		String string = "aaab";
		String string = "0100110001010001";
		String subString = null;
		int size = string.length();
		for (int length = 1; length <= size; length++) {
			for (int index = 0; index <= (size - length); index++) {
				subString = string.substring(index, index + length);
				if (!list.contains(subString)) {
					list.add(subString);
				}
			}
		}
		System.out.println(list.size());
		System.out.println(list.toString());
	}
}


试题C:数列求和


问题描述：

给定数列 1, 1, 1, 3, 5, 9, 17, …，从第 4 项开始，每项都是前 3 项的和。求 第 20190324 项的最后 4 位数字。


public class Main {
	public static void main(String[] args) {
		int number = 20190324;
		
		long num1 = 1;
		long num2 = 1;
		long num3 = 1;
		long temp = 0;
		
		// 首先使用较小的项数测试完整的数字，与下面截取的结果进行比较
//		for (long i = 4; i <= 50; i++) {
//			temp = num3;
//			num3 = (num1 + num2 + num3);
//			num1 = num2;
//			num2 = temp;
//		}
		
		for (long i = 4; i <= number; i++) {
			temp = num3 % 10000;
			num3 = (num1 + num2 + num3) % 10000;
			num1 = num2 % 10000;
			num2 = temp;
		}
		System.out.println(num3);
	}
}


 当时试过用递归，但是对于20190324这样的项数，直接就报了栈溢出。所以试验了上面代码中注释掉的部分，直接使用了20190324跑的结果5268603393216230115，这个结果看上去还可以，但唯独千位数是0，很郁闷，用20190325跑了一次发现数值越界了（结果是-94021825125598091），当时自作聪明地以为20190324就是临界值。/泪奔


 试题D:数的分解


问题描述：

把 2019 分解成 3 个各不相同的正整数之和，并且要求每个正整数都不包 含数字 2 和 4，一共有多少种不同的分解方法？ 注意交换 3 个整数的顺序被视为同一种方法，例如 1000+1001+18 和 1001+1000+18 被视为同一种。

蓝桥备考基础算法归纳
暴力、贪心
递归、递推
二分、快排
深度优先搜索、广度优先搜索、回溯
字符串处理

双指针

动态规划

各类背包问题

数论

全排列、组合
素数、最大公约数、最小公倍数、欧几里得gcd
海伦公式、斐波那契、杨辉三角
大整数

图论
C++ STL类库使用
一些小点
scanf("%[^\n]", &ch);
scanf中正则表达式的输入格式

接收除了回车以外的所有字符