关键词：
参考技术A 字符串的匹配在Java中都知道使用indexOf函数来实现，那么其匹配算法是怎么样的呢？单模式和多模式的区别就是一次遍历主串能否将多个模式的字符串都查找出来。
英文全称为Brute Force，暴力匹配算法，匹配字符串的方法比较暴力，也比较简单易懂。其大概的思路就是：
我们可以看到，在极端情况下，在主串 aaaa...aab 中寻找模式串 aab ，那么总共需要寻找(n-m+1)次，且每次都需要比对m次，那么时间复杂度将是 (n-m+1)*m ，即 O(n*m) ；但实际上并不会这么低效，因为我们的使用场景中主串和模式串都不会太长，而且在每个子串和模式串进行比对时，只要中途有一个不匹配，那么当前比对就会提前结束，因此大部分情况下，时间复杂度都会比 O(n*m) 要好。
我们在BF算法的基础上引入哈希算法，我们不需要将每个子串与模式串逐个字符地进行比较，而是计算得出每个子串的hash值，然后和模式串的hash值进行比较，如果有相等的，那就说明有子串和模式串匹配上了。
虽然我们只需要比对模式串和子串的hash值就能得到匹配结果，次数为(n-m+1)，但是对每个子串进行hash计算的时候，是要遍历每个字符的，因此次数也是m，那么总的时间复杂度还是 O(n*m) ，并没有明显地提升。
那么我们该如何想出一个办法，使得每个子串hash值的计算时间得到提升呢？这就是RK算法的精髓，假设子串包含的字符集中元素个数为k，那么就用k进制数来代表这个子串，然后hash的过程就是将这个k进制的数转换为十进制的数，这个十进制的数就是该子串的hash值。
相邻子串的hash值计算是有规律的，我们只需要遍历一次主串就能得到所有子串的hash值，算法复杂度为O(n)，而不是像原先一样，每个子串都需要O(m)的时间复杂度。
然后将模式串的hash值和所有子串的hash值进行比较，每次比较的时间复杂度是 O(1) ，总共比较(n-m+1)次，所以RK算法的总的时间开销为 O(n)+O(1)*O(n-m+1) ，即为 O(n) ，时间复杂度比BF算法更加高效。
当然，有hash的地方就有可能会存在hash冲突，有可能子串和hash值和模式串的hash值是一样的，但内容就是不一样，此时怎么办呢？其实很简单，对于hash值一样的子串，我们增加双保险，再比较一下这m个字符是否都一样即可，总的时间开销为 O(n)+O(1)*O(n-m+1)+O(m) ，即为 O(n) 。
如果极端情况下出现了很多hash冲突呢？我们对于每个和模式串相同hash值的子串都需要逐一再进行比较，那么总的时间开销就会为 O(n)+O(1)*O(n-m+1)+O(m)*O(n-m+1) ，即为 O(n*m) ，不过这种概率太小了，大部分情况下都不会这样。
在真正的文本编辑器中查找和替换某个字符串时，使用的算法既不是上述的BF算法，也不是RK算法；BF算法只适合不是很长的主串，RK算法则要设计一个冲突概率很低的hash算法，这个比较困难，所以实际使用的是BM算法，它是工程中非常常用的一种字符串匹配算法，效率也是最高的。
算法的思想和过程有些复杂，待以后整理。
KMP算法在本质上是和BM算法一样的。算法的思想和过程有些复杂，待以后整理。
浏览器输入框中的智能输入匹配是怎么实现的，它是怎么做动态字符串匹配查找的呢？这就用到了Trie树。
又名字典树，是一种专门用来快速查找字符串前缀匹配结果的树形结构，其本质就是将所有字符串的重复的前缀合并在一起，构造一个多叉树。
其中，根节点不包含任何信息，每个节点表示一个字符，从根节点到红色节点的一条路径表示存储的一个字符串。当我们在如上Trie树中查找"he"时，发现"he"并非是一个字符串，而是"hello"和"her"的公共前缀，那么就会找到这两个字符串返回。
Trie树在内存中是如何存储的呢？因为每一个节点都可能是包含所有字符的，所以每一个节点都是一个数组（或者散列表），用来存储每个字符及其后缀节点的指针。
使用Trie树，最开始构建的时候，时间复杂度为 O(n) ，其中n为所有字符串长度之和，但是一旦构建完成，频繁地查询某个字符串是非常高效的，时间复杂度为 O(k) ，其中k为查找字符串的长度。
Trie树虽然查询效率很高，但是比较浪费内存，每一个节点都必须维护一个数组存放所有可能的字符数据及其指向下一个节点的指针，因此在所有字符串公共前缀并不多的时候，内存空间浪费地就更多了。这种问题其实也有对应的解决办法，我们可以不使用数组，而是使用有序数组、散列表、红黑树来存放，可以相应地降低性能来节省内存空间。
Trie树除了可以实现浏览器动态输入内容查找候选项的功能外，还可以实现多模式地敏感词匹配功能。假设我们需要对用户输入的内容进行敏感词检查，将所有的敏感内容用***代替，那么该如何实现呢？
首先我们可以维护一个敏感词字典，使用上述四种单模式匹配算法也可以实现，但是需要遍历N次用户输入的内容，其中N是所有敏感词的模式串，显得非常低效。但是我们如果将敏感词字典维护为一个Trie树，然后将用户输入的内容从位置0开始在Trie树中进行查询，如果匹配到红色节点，那么说明有敏感词；如果没有匹配到红色节点，就从用户输入内容的下一个位置开始继续在Trie树中查询，直至将用户输入内容遍历完，因此我们只是遍历了一遍主串。
然而更高效的多模式字符串匹配使用地更多的是如下的AC自动机。
如果把Trie树比作BF算法，KMP算法是BF算法的改进，那么AC自动机就是利用同样的思想改进了Trie树。
算法的思想和过程有些复杂，待以后整理。
数组黑科技（偏性能方面）未完待更新...
数组去重最优解：Array.prototype.unique=function()vartmp=newMap();returnthis.filter(item=>return!tmp.has(item)&&tmp.set(item,1);) 查看详情
centos6最小化安装所需的常用软件（未完待更新）
CentOS6最小化安装，缺少常用的软件，软件列表如下：yuminstalllrzszwgettelnetlsof openssh-clients-ylrzsz-->rzsz命令wget-->wget命令telnet -->telnet命令lsof -->lsof命令openssh-clientsscp命令,两端的服务器都需要安装这个包 查看详情
字符串匹配--kmp算法原理整理
...原理:求出P0···Pi的最大相同前后缀长度k；字符串匹配是计算机的基本任务之一。举例,字符串"BBCABCDABABCDABCDABDE"，里面是否包含另一个字符串"ABCDABD"？许多算法可以完成这个任务，Knuth-Morris-Pratt算法（简称KMP）是最... 查看详情
kmp算法-未完(代码片段)
...的长度,要注意应用中提出的nxt[i]变化（方便在匹配两个字符串时候跳动减少时间复杂度)nxt数组模板：以i=1为起点的字符串进行处理voidget_nxt()nxt[0]=nxt[1]=0;for(inti=2,j=0;i<=m;++i)while(j&&b[j+1]!=b[i])j=nxt[j];//交换后从头再次匹配前... 查看详情
漫谈回溯(未完待续)
将不使用优化算法、直接用朴素算法来解决问题的做法称为暴力法。回溯是带优化的穷举。回溯是具有界限函数的深度优先搜索。 查看详情
前端html与css整理（未完）
HTML中的标签存放于文本文件中需要按照以下固定的文档结构组织：<!DOCTYPEHTML><html><head>头部相关信息</head><body>页面主体相关内容</body></html>标签解释：#1、<!DOCTYPEHTML>是文档声明，必须写在HTML... 查看详情
算法面试题整理(代码片段)
1、python反转字符串‘‘‘第一种：使用字符串切片‘‘‘s=‘HelloWorld‘print(s[::-1])#dlroWolleH‘‘‘第二种：使用列表的reverse方法‘‘‘l=list(s)l.reverse()print("".join(l))#dlroWolleH‘‘‘第三种：使用reduce‘‘‘fromfunctoolsimportreduceresul... 查看详情
kmp--字符串匹配
现在计算机处理涉及到大量的字符串操作，字符串的匹配是使用频率最高的字符串操作之一，大学数据结构与算法中字符串一章，也专门介绍了字符串匹配。字符串的单模式匹配中最基础的算法是朴素的模式串匹配算法，比这更... 查看详情
rxjava整理(未完)(代码片段)
一、定义RxJava 是一个 基于事件流、实现异步操作的库。二、gradle配置implementation'io.reactivex.rxjava3:rxjava:3.0.0'三、Rxjava相关操作符介绍1.创建操作符。1.create()创建被观察者对象。privatefundoRxJavaCommonTest()Observable.create(ObservableO... 查看详情
漫画：如何优化“字符串匹配算法”？(代码片段)
漫画：如何优化“字符串匹配算法”？说起“字符串匹配”，恐怕算得上是计算机领域应用最多的功能之一，为了满足这一需求，聪明的计算机科学家们发明了许多巧妙的算法。在上一篇漫画中，我们介绍了BF算法和RK算法，没... 查看详情
“模糊匹配”字符串的算法
】“模糊匹配”字符串的算法【英文标题】：Algorithmsfor"fuzzymatching"strings【发布时间】：2011-02-2221:45:29【问题描述】：通过模糊匹配，我并不是指Levenshtein距离或类似的字符串，而是它在TextMate/Ido/Icicles中的使用方式：给... 查看详情
字符串匹配的kmp算法
字符串匹配是计算机的基本任务之中的一个。 举例来说，有一个字符串"BBCABCDABABCDABCDABDE"。我想知道。里面是否包括还有一个字符串"ABCDABD"？ 很多算法能够完毕这个任务，Knuth-Morris-Pratt算法（简称KMP）是... 查看详情
字符串的模式匹配：rk算法
RK算法是由Rabin和Karp共同提出的一个算法。 RK算法是对BF算法的一个改进：在BF算法中，每一个字符都需要进行比较，并且当我们发现首字符匹配时仍然需要比较剩余的所有字符。而在RK算法中，就尝试只进... 查看详情
首次出现的并行字符串匹配算法
】首次出现的并行字符串匹配算法【英文标题】：First-OccurrenceParallelStringMatchingAlgorithm【发布时间】：2011-01-1920:25:45【问题描述】：首先，这是功课。话虽如此，它是非常开放的，对于如何开始思考这个问题（或一般的并行算法... 查看详情
图解数据结构与算法数据结构与算法知识点整理datastructuresandalgorithms
...哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法等。我们可以通过学习数据结构和算法来编写高效和优化的计算机程序。一旦了解了不同的数据结构和算法，就可以决定在不同的情况下使用哪种数据结构... 查看详情
javascript学习笔记整理day10
一.正则表达式（规则表达式） 定义：使用单个字符串来描述、匹配一系列符合某个语法规则的字符串搜索模式二.正则表达式的作用 操作字符串是正则的唯一作用（验证用户名，验证电话号码，验证密码等表单元素... 查看详情
常用算法3-字符串查找/模式匹配算法（bf&kmp算法）
...linux是如何在浩如烟海的文本中正确匹配到我们所需要的字符串呢？这就牵扯到了模式匹配算法！1.模式匹配什么是模式匹配呢？模式匹配，即子串P(模式串)在主串T(目标串)中的定位运算，也称串匹配假设我们有两个字符串：T(Tar... 查看详情
字符串暴力匹配算法详解(代码片段)
字符串暴力匹配算法详解说明字符串暴力匹配算法是指在一个长字符串中暴力寻找是否包含某一子串所谓暴力匹配，就是不使用任何其他算法，将两个字符串中的字符一一进行比对从长字符串的第一个字符开始，判断是否和子字... 查看详情