关键词：
不得不说ACM哪怕是没有结果，对于算法能力的训练是毋庸置疑的……
因为老师划了重点，所以讲一下horspool的字符串匹配算法的原理吧。
先声明几个概念，被找的字符串称为匹配串，要找的字符串被称为模式串，当前和模式串相匹配的匹配串的子串被称为匹配子串（废话
在朴素算法中，我们要找一个匹配串是否存在模式串，例如HuangZhi is a genius的匹配串串和ChengJinSen的模式串，那么我们一开始用的方法是用：
HuangZhi is(11 character)
去匹配：
ChengJinSen（11 character）
如果每个字母都相等，那么我们就认为这个模式找到了。
但是这个算法的效率是多少呢，假设匹配串的长度为N,模式串的长度为m,那么易证时间效率为：O(n*m)，在很多时候这个效率都是很慢的。
而Horspool算法（在我看来）是有这样一个基本思想：如果我提前知道了这个步骤是可以跳过的，那我就可以不用去验证了。
我们拿saber和archer作为模式串和匹配串好了：
archer
saber
很明显，在初次对齐的时候，其并不相等，而且我们注意到了，此次匹配串对应的子串是：arche,而最后一个字母是e.
那么很明显的，假如我们一个个移动下去，直到模式串的下一个e为止，都不可能达到匹配的结果。
这里e就是下一个，所以我们把saber稍稍的改一下，改成sebar,这时候就会发现，假设你一个个挪，到e之前的所有都不可能和arche里的e匹配，所以这里我们完全可以直接把e挪到arche的e的位置，然后在进行匹配计算，这样就节省了不少的时间。也就是说，跳过e到模式串最后一个字母之间的距离。
以上的情况，可以归纳为情况1，即匹配子串的最后一个在模式串中出现过，且不是模式串的最后一个字母（最后的特殊性会讲到）
那么，假设最后一个字符在模式串里从来没有出现过呢？那这样，假设一个个移，每一个都必然得不到匹配结果，直到该字符不在匹配子串中，如此，则是直接跳过整个子串的长度。
以上情况归为情况2，匹配子串的最后一个字母没有在模式串里出现过，且不是模式串的最后一个字母。
好了，为什么上面要提到模式串的字母呢？因为这个查询方法存在一个问题，假设匹配子串的最后一个字母在模式串中出现过，且为模式串的最后一位呢？那这样就要分成两种情况来讨论，
1，是模式串的最后一位字母在模式串中唯一，那这样就类似于情况2，直接跳过这个匹配子串最后字母的匹配，即跳过字符长度。这个我们姑且称为情况3。
2，是该字母在模式串中不唯一，那这样就仿照情况二，找到离模式串结尾最近的，且同样是这个字母的字母的位置，并跳转以后匹配。这个我们称为情况4
然后是这个算法的计算机实现，总结了下上述规律，我们发现这个模式串跳转的机制，可以不用每次查找模式串中是否有同样的值，而用预处理的方式来实现，根据情况一二的总结，我们得出，模式串中存在的字母，向右找到其最贴近模式串结尾的同样的字母，并把其离结尾的位置存下，方便应用，若不存在，则直接跳转模式串长度，为了方便，我们也把它存下来，不过跳转长度设为模式串长度。根据情况3,4的总结，我们得出，最后一个字母不应纳入上述的计算。
附带试验用算法：
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<string>
#define INF 0x3f3f3f3f
using namespace std;
int main() {
string M, P;
cin >> M >> P;
map<char, int>NEXT;
for (int i = 0; i < 26; i++)
NEXT[‘a‘ + i] = P.size();
for (int i = 0; i < 26; i++)
NEXT[‘A‘ + i] = P.size();
for (int i = 0; i < P.size() - 1; i++)
NEXT[P[i]] = P.size() - i-1;
int space = 0;
for (int i = 0; i <= M.size()-P.size();)
{
space = i;
cout << M << endl;
for (int i = 0; i < space; i++)
cout << " ";
cout << P << endl << "_________________________________" << endl;
if (M.substr(i, P.size()) == P)
cout << "找到匹配串" << endl;
i += NEXT[M[i + P.size() - 1]];
}
}
horspool算法(代码片段)
概念horspool算法为字符串匹配算法，这是一个空间换时间的算法，算法把模式和文本的开头字符对齐，从模式的最后一个字符开始比较，如果尝试比较失败了，它把模式向后移。每次尝试过程中比较是从右到左... 查看详情
哪个是更好的字符串搜索算法？ Boyer-Moore 还是 Boyer Moore Horspool？ [关闭]
】哪个是更好的字符串搜索算法？Boyer-Moore还是BoyerMooreHorspool？[关闭]【英文标题】：Whichisabetterstringsearchingalgorithm?Boyer-MooreorBoyerMooreHorspool?[closed]【发布时间】：2012-07-1223:23:28【问题描述】：BoyerMoore算法的预处理时间为Θ(m+|Σ|)... 查看详情
哪个是更好的字符串搜索算法？ Boyer-Moore 还是 Boyer Moore Horspool？ [关闭]
】哪个是更好的字符串搜索算法？Boyer-Moore还是BoyerMooreHorspool？[关闭]【英文标题】：Whichisabetterstringsearchingalgorithm?Boyer-MooreorBoyerMooreHorspool?[closed]【发布时间】：2012-07-1219:29:48【问题描述】：BoyerMoore算法的预处理时间为Θ(m+|Σ|)... 查看详情
horspool算法（java）随机生成字符串
java代码importjava.util.Scanner;publicclassHorspool{publicstaticvoidShiftTable(char[]p,int[]table){for(inti=0;i<26;i++){table[i]=p.length;}for(inti=0;i<p.length-1;i++){table[p[i]-‘A‘]=p.leng 查看详情
正则引擎在数据包匹配中的工程分析
匹配 常见的通用匹配算法有字符串匹配和正则匹配。字符串匹配常见的算法有Boyer-Moore算法、orspool算法、unday算法、MP算法、R算法、AC自动机。Boyer-Moore、Horspool、Sunday算法都是基于后缀数组的匹配算法，区别在于移动的方式不一... 查看详情
字符串的模式匹配：horsepool算法
Horsepool算法是Boyer-Moore算法的简化版本，这也是一个空间换时间的典型例子。算法把模式P和文本T的开头字符对齐，从模式的最后一个字符开始比较，如果尝试比较失败了，它把模式向后移。每次尝试过程中比... 查看详情
字符串匹配算法(代码片段)
字符串匹配算法 原文摘录：https://www.cnblogs.com/gaochundong/p/string_matching.html首先是一系列概念定义：文本Text:是一个长度为n的数组T[1..n] (??这里第一位置索引是数字1)模式Pattern:是一个长度为m的数组P[1..m], 并且m<=n.T和P... 查看详情
uva11488hyperprefixsets字典树
...子讲课的笔记Trie三兄弟——标准Trie、压缩Trie、后缀Trie字符串模式匹配算法——BM、Horspool、Sunday、KMP、KR、AC算法一网打尽#include<bits/stdc++.h>usingnamespacestd;constintMAX=5e4+5 查看详情
字符串匹配算法
字符串匹配算法总结(转)查找——图文翔解RadixTree（基数树） 查看详情
字符串模式匹配算法sunday算法
Sunday算法的思想类似于BM算法中的坏字符思想。差别在于Sunday算法在失配之后，是取目标串中当前和模式串匹配的部分后面一个位置的字符来做坏字符匹配。 举例： BM算法在b与x失配后，坏字符为b(下标1)，在模... 查看详情
算法基础-朴素模式匹配算法、kmp模式匹配算法
参考技术A假设我们要从主字符串goodgoogle中匹配子字符串google朴素模式匹配算法就是通过从主字符的头部开始一次循环匹配的字符串的挨个字符如果不通过则主字符串头部位置遍历位置+1在依次遍历子字符串的字符匹配过程主字... 查看详情
字符串匹配算法——kmp算法
1、字符串匹配字符串匹配是计算机的基本任务之一。字符串匹配是什么？举例来说，有一个字符串"BBCABCDABABCDABCDABDE"，我想知道，里面是否包含另一个字符串"ABCDABD"？许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是... 查看详情
字符串匹配算法(代码片段)
1.1BF算法其实就是暴力解法，直接双重循环，干就完事了。虽然算不上什么好方法，但是非常简单。对于所有的暴力算法，我们应该思考如何进行优化，比如BF算法，当我们遇到不匹配字符的时候，只能从头的下一个字符开始匹... 查看详情
kmp算法字符串匹配算法(代码片段)
简介字符串的模式匹配是对字符串的基本操作之一，广泛应用于生物信息学、信息检索、拼写检查、语言翻译、数据压缩、网络入侵检测等领域，如何简化其复杂性一直是算法研究中的经典问题。字符串的模式匹配实质上就是寻... 查看详情
字符串匹配---kmp算法
字符串匹配---KMP算法 来源-http://blog.csdn.net/ebowtang/article/details/49129363前言 KMP算法是一种改进的字符串匹配算法，由D.E.Knuth，J.H.Morris和V.R.Pratt同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称KMP算法）... 查看详情
字符串的模式匹配：sunday算法
Sunday算法是DanielM.Sunday于1990年提出的字符串模式匹配。其核心思想是：在匹配过程中，模式串发现不匹配时，算法能跳过尽可能多的字符以进行下一步的匹配，从而提高了匹配效率。其效率在匹配随机的字符... 查看详情
字符串匹配算法之kmp算法
kmp算法是一种效率非常高的字符串匹配算法，是由Knuth，Morris，Pratt共同提出的模式匹配算法，所以简称KMP算法算法思想在一个字符串中查找另一个字符串时，会遇到如下图的情况我们通常的做法是从第一个串A的下一位B再逐位比... 查看详情
漫画：如何优化“字符串匹配算法”？(代码片段)
漫画：如何优化“字符串匹配算法”？说起“字符串匹配”，恐怕算得上是计算机领域应用最多的功能之一，为了满足这一需求，聪明的计算机科学家们发明了许多巧妙的算法。在上一篇漫画中，我们介绍了BF算法和RK算法，没... 查看详情