首页 / 算法 / 字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含9674字，纯文字阅读大概需要14分钟。

内容图文

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法

常见字符串问题:

闲言少叙，我们直接来解决下面几个问题。

给定字符串s，t，求t在s中匹配的子串位置

给定一个字符串s，求最长回文子串

给定字符串s，t，最长公共连续子串问题

对于问题1，也叫exact matching问题。

朴素的解法是依次从s的起始位置出发，依次比较跟t长度相同的子串，此算法复杂度为O(N*M)，空间复杂度为O(M)，确切的说是单个t的长度。

对此的解决方法有:

KMP算法: Knuth-Morris-Pratt，最差O(N+M)的复杂度

Boyer-Moore算法: BM算法，最差是线性,可能是次线性的复杂度。

Apostolico-Giancarlo算法: 有BM算法的效率,而且相对简单的证明最差线性复杂度（介绍如此，实际并不）

对于问题2，

参考：

algorithms-on-strings-trees-and-sequences，Cambridge University Press，1997

KMP算法：

应用

Knuth-Morris-Pratt算法，求子串匹配的问题。

leetcode中的题目5正是它的最直接应用；

题目中提到haystack，needle，分别对应文本和模式串，是英语中的"谷堆取针"，或大海捞针之义。我们用s、needle表示。

性质

KMP算法通过预处理模式串，记录每个模式串位置下的前驱位置，保存在数组中。

匹配的时候，s、needle往后遍历，字符失配的时候needle根据next数组跳转回上一步；由于原始的KMP算法中用到公共前后缀长度的思路，如果失配返回上一次位置仍然可能进行回退，所以有第二个优化版本如下。s是一直递增的，而needle每次操作不超过1次，所以最大复杂度为O(N)。

if (x[i] == x[j])
   kmpNext[i] = kmpNext[j];
else
   kmpNext[i] = j;

关于跳转的原理，可以见下面的链接。

代码

void preKmp(string x, vector<int>& kmpNext) {
    int i, j;
    int m = x.size();
    i = 0;
    j = kmpNext[0] = -1;
    while (i < m - 1) {
      while (j > -1 && x[i] != x[j])
         j = kmpNext[j];
      i++;
      j++;
      if (x[i] == x[j])
         kmpNext[i] = kmpNext[j];
      else
         kmpNext[i] = j;
    }
    for (int i = 0; i < m; i++) {
        printf("[%d %d]", i, kmpNext[i]);
    }
    printf("\n");
}

void KMP(string x, int m, string y, int n) {
    int i, j;
    vector<int> kmpNext(m);

    /* Preprocessing */
    preKmp(x, kmpNext);

    /* Searching */
    i = j = 0;
    while (j < n) {
      while (i > -1 && x[i] != y[j])
         i = kmpNext[i];
      i++;
      j++;
      if (i >= m) {
         printf("match %d\n", j - i);
         i = kmpNext[i];
      }
    }
}

// void expect_test(string a, string b) {
// assert(a == b);
// }

int main() {
    string s, pattern;
    cin >> s >> pattern;
    clock_t t1 = clock();
    KMP(s, s.size(), pattern, pattern.size());
    double sec = (clock() - t1) / CLOCKS_PER_SEC;
    printf("match %.2fs", sec);
    return 0;
}

术语解释

失配：遍历串的时候比较发现两个字符不相等，称为失配；

模式串：如果想判断字符串s中是否包含字符串t，则t称为模式串，而s称为文本串。

文本串：如上

http://wiki.jikexueyuan.com/project/kmp-algorithm/define.html

Boyer-Moore算法

概念

好后缀：只要清楚了失配的概念就知道了，好后缀是根据模式串后缀的下标移动位数的数组；

坏字符：根据失配的时候推理出的结果。

性质

预处理要开bmBc，bmGs，suffix三个数组，但是只是模式串的，如果模式串可控，在实际中还是可应用的。编辑器的文字匹配常用的算法。

Manacher算法：

Manacher算法用来求最大回文子串。

对字符串做预处理，在每个字符的两边都插入'#'，使得字符串长度为奇数(除非是空串，但是可以处理)。该处理的意义是方便每次都有一个中心点，以做左右对称的计算。

思路是遍历字符串，更新最大回文的右边界R和最大的半径、中心点C，在过程中得到最大的半径。当前位置最大半径的更新来自记录的最大半径值，可分两组情况讨论，即左对称点的最大回文范围是否已在大半径内，如果是直接用其更新，否则就扩展到后面直到不匹配；

图1是落在半径内的结果，计算方法为：p[i] = R > i ? min(p[2 * C - i], R - i) : 1;

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法 - 文章图片

图2 最大回文范围的一种情况

知道p之后可以更新对应的最大字符串。

算法的实现如下：

#include <bits/stdc++.h>

using namespace std;
int manacher(string& s, vector<int>& segment) {
    /*
    忽略s=""的情况
    */
    int n = s.size();
    string new_s = "#";
    for (int i = 0; i < n; i++) {
        new_s += s[i];
        new_s += '#';
    }
    int R = 0, C = 0;
    int mx = 0;               //最大半径
    vector<int> p(2 * n + 1); //每个位置为中心的最大回文半径
    int len = 2 * n + 1;
    int cx = -1;
    for (int i = 0; i < len; i++) {
        p[i] = R > i ? min(p[2 * C - i], R - i) : 1;
        while (i - p[i] >= 0 && i + p[i] < len && new_s[i - p[i]] == new_s[i + p[i]]) {
            p[i]++;
        }
        if (i + p[i] > R) {
            C = i;
            R = i + p[i];
            if (p[i] > mx) {
                mx = p[i];
                cx = C;
            }
        }
    }
    segment[0] = (cx - mx + 1) / 2; //修改后的串起始位置除以2恢复原位置
    segment[1] = mx - 1;
    printf("%d %d\n", mx, R);
    return 0;
}


int main() {
    string s;
    while (cin >> s) {
        vector<int> segment(2); //[起始位置,长度]
        manacher(s, segment);
        cout << segment[0] << " " << s.substr(segment[0],
        segment[1]) << endl;
    }
    return 0;
}

代码中返回的结果为最大回文子串的第一个结果。

一些细节

1.有实际意义的一般不是求最大长度，所以用segment记录起始位置和长度，以打印子串。

2.处理后的字符串中，像#a#b#b#a#的奇数位为1。

3.空串也可以处理，反正返回0了。

4.插入的结果不要求是字符串中没出现的，只是惯例是插入#。

5.中心点c的左右对称坐标a,b满足a+b=2c,这是几何性质。

上图2用到了以下博客的图：

Manacher 算法，刘毅，https://subetter.com/algorithm/manacher-algorithm.html

AC自动机:

应用

Aho-Corasick: KMP的改良算法，用来进行多模式匹配的。所谓的多模式匹配，是说给定n个模式串pattern，一个文本串，求文本串里匹配了多少个模式串（顺带也可以求出具体串）。

如果你不懂trie树和kmp算法，请先了解相关知识。AC自动机中包含了类似的思想。

实现思路如下：

根据pattern构建一个DFA（如果只考虑实线，它就是一棵trie树），参考下图或其他博客：

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法 - 文章图片

图2 构建的DFA

性质

内部实现经常会提到goto表，failure表，但是这只是个抽象，trie树中没有直接的表，而是存了一些状态转移的数组在结构中；

由于前人之述备矣，这里只是提出几个AC自动机的问题：

1. AC自动机也有naïve方式的实现，例如只处理26个字母的；但是AC自动机如果要实现任意ascii和unicode的转移，不能采用简单的256或65536大小的数组，一般是采用Map<Character, State>，但是空间、时间效率无法同时保证，解决方法看第4点，只要O(1)的时间复杂度和必要的空间复杂度即可进行状态转移；

2.处理过程包括了预处理success转移、output数组、BFS构建failure数组；

3.AC自动机可以跟线段树组合实现文本字符串中所有位置的模式匹配报告；

4.可以参考hankcs网站上的AC自动机、AC自动机的双数组trie、分词器、，其中也参考了一个日本人的实现。利用双数组trie树，可以高效地实现状态转移。

假设现在已经实现了一个AC自动机，其用法如下：

List<String> patterns = {"he", "his", "her", "hers"};
ACTrie trie = new ACTrie();
trie.build(patterns);
String text = "ushers";
res = trie.parseText(text);

双数组trie:

应用

双数组trie是用来压缩Trie空间的。

双数组Trie的一种实现 An Implementation of Double-Array Trie https://www.cnblogs.com/DjangoBlog/p/4072972.html

以上文章阐明了双数组trie树的来历，利用双数组trie树可以用来提供trie树的状态转移功能。其原理是既然有s到t的转换，则以s的地址加字符作为新状态的下标。这个是跟普通的AC自动机生成状态下标的过程不同的。

而check[t]记录了转移到该状态的前一个状态下标。

为什么要用到base数组?可以举一个例子,插入字符编码为'A'和2的数字后我们得到了

base[state('A')] + code[20] = base[state('A' + 20)]；这里base[state('A' + 20)]中的下标是个字符串的状态,而base[i]是个int。那么该int值是固定的吗?是的,因为该状态只能从上一个状态string('A')唯一得来。但是反之我们遇到该状态的int值,不一定代表上一个状态就是'A'。

例如若base['B'] = 'A' + 2(该情况是可以满足的),那么base[state('B'.concat(18))] = base[state('B')] + code[18] = base['A'] + code[2 + 18] = base[state('A'.concat(20))]

解决该问题可以额外增加一个check数组,因为每个状态的前继是唯一的。

状态转移如图：

check[base[s] + c] = s
t = base[s] + c

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法 - 文章图片

由于要区分初始节点，初始化了base[0] = 1, check[0] = 0，如下所示，这里的状态转移是加c+1而不是c。双数组trie的实现不是唯一的，包括要校验的位置可以不是s而是base[s]，但是要保证check[t]位置保存的时候也是base[s]。

    protected int transitionWithRoot(int nodePos, char c)
    {
        int b = base[nodePos];
        int p;
        p = b + c + 1;
        if (b != check[p])
        {
            if (nodePos == 0) return 0;
            return -1;
        }
        return p;
    }

后缀自动机：

应用

后缀数组、后缀自动机可以解决大字符串的LCS问题（小的可以用动态规划和暴力解决）

suffix automata，SAM。为了解决后缀树构造和查询时，时间复杂度和空间复杂度过大的的问题。好了，那为什么要构造后缀树？因为它能解决最长回文、最长公共子串、唯一子串种类等问题。

后缀自动机是一个基于trie的字符串有向图，时间和空间复杂度均为O（N）。

基本概念

后缀自动机一·基本概念 http://hihocoder.com/problemset/problem/1441

构成DFA的五元组 <字符集，状态集，转移函数、起始状态、终结状态集>

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法 - 文章图片

图3 后缀自动机

子串的结束位置集合endpos，即子串在原串中所有出现地方的右端下标；每个DFA状态中包含所有具有相同endpos的子串。

性质1：每个到终点的路径都是原串的后缀，否则不是后缀。

性质2：每个状态可能代表多个子串，而且要用到某个状态中的最长子串，最短子串。

LCS问题

解决LCS问题可以用后缀自动机、后缀树。

以下代码：

struct SAM {
    SAM *pre,*son[26];
    int len,g;
} que[N],*root,*tail;
int tot;
void add(int c,int l) {
    SAM *p=tail,*np=&que[tot++];
    np->len=l;
    tail=np;
    while(p&&p->son[c]==NULL) p->son[c]=np,p=p->pre;
    if(p==NULL) np->pre=root;
    else {
        SAM *q=p->son[c];
        if(p->len+1==q->len) np->pre=q;
        else {
            SAM *nq=&que[tot++];
            *nq=*q;
            nq->len=p->len+1;
            np->pre=q->pre=nq;
            while(p&&p->son[c]==q) p->son[c]=nq,p=p->pre;
        }
    }
}
char a[N/2],b[N/2];
int lcs(char a[],char b[]) {
    memset(que,0,sizeof(que));
    tot=0;
    root=tail=&que[tot++];
    for(int i=0; a[i]; i++) add(a[i]-'a',i+1);
    SAM *p=root;
    int ans=0;
    for(int i=0,l=0; b[i]; i++,ans=max(ans,l)) {
        int c=b[i]-'a';
        if(p->son[c]) p=p->son[c],l++;
        else {
            while(p&&p->son[c]==NULL) p=p->pre;
            if(p==NULL) p=root,l=0;
            else l=p->len+1,p=p->son[c];
        }
    }
    return ans;
}

这里面http://devhui.com/2015/04/21/Longest-Common-Substring/ 抄了Byvoid和陈立杰的。

以上代码存在的问题

显然它就是处理naïve情况下的自动机的，只处理a-z的字符；

不是动态大小的自动机，一开始就占用了空间。

不过都可以解决。

具体原理参考陈立杰的后缀自动机的讲稿。

References:

[1] algorithms-on-strings-trees-and-sequences，Cambridge University Press，1997

[2]EXACT STRING MATCHING ALGORITHMS (KMP, BM) http://www-igm.univ-mlv.fr/~lecroq/string/index.html

[3] Manacher 算法，刘毅，https://subetter.com/algorithm/manacher-algorithm.html

[4] http://devhui.com/2015/04/21/Longest-Common-Substring/

[5] AC自动机模板(【洛谷3808】),

小蒟蒻yyb ,https://blog.csdn.net/qq_30974369/article/details/74557224

[6] Aho Corasick自动机结合DoubleArrayTrie极速多模式匹配,hankcs（何晗）,

http://www.hankcs.com/program/algorithm/aho-corasick-double-array-trie.html

[7] 后缀自动机一·基本概念 http://hihocoder.com/problemset/problem/1441

内容总结

以上是互联网集市为您收集整理的字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法全部内容，希望文章能够帮你解决字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法所遇到的程序开发问题。如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/692188.html

来源：【匿名】

【上一篇】十大经典排序算法最强总结（含JAVA代码实现）【下一篇】浅谈php实现映射的两种方法（链表和二叉树）

更多 ►

【字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法】教程文章相关的互联网学习教程文章

字符串数据结构算法题-C++【代码】

1）最长不重复子串使用string和vector<string>string FindLongestNonRepeatSubstring(string str) {if (str.empty()) return"";string tmp;//存放临时不重复的子串vector<string> svec;//存放所有不重复的子串int start = 0;//标记每次开始查找子串的下标int pos = -1; //查找当前字符在子串中的位置下标tmp.push_back(str[0]);for (unsigned int i = 1; i < str.size(); ++i){pos = tmp.find(str[i]);if (pos == -1){tmp.push_bac...

103-算法应用【字符串反转】代码实现【代码】

字符串反转本文链接：https://www.cnblogs.com/cheng2839 介绍将字符串倒序组织分析我们都知道StringBuilder类有个reverse()方法，可以将字符串反转，但这里考察的是算法实现。所以我们采取链表存储字符串，然后将链表反转。实现下面是用java实现算法： //本文链接https://www.cnblogs.com/cheng2839publicclass $Convert {//反转方法publicstatic Entry convert(Entry root) {if (root == null)returnnull;Entry i = root, j = ...

字符串模式匹配算法2 - AC算法【代码】【图】

讨论QQ群：135202158 上篇文章（http://www.cnblogs.com/zzqcn/p/3508442.html）里提到的BF和KMP算法都是单模式串匹配算法，也就是说，模式串只有一个。当需要在字符串中搜索多个关键字（模式）时，则需要用到多模式串匹配算法。AC（Aho-Corasick）算法是一个经典的多模式串匹配算法，它借鉴了KMP算法的思想，可以由有限状态机（Finite State Automata：FSA）来表示。AC算法的基本原理是：先根据多模式串建立一个有限状态自动机FS...

字符串匹配算法（在字符串T中查找是否有与字符串P相同的子串）

T称为目标串（Target）或主串，P称为模式串（Pattren）或子串 1、简单字符串模式匹配算法原理：用字符串P的字符依次与字符串T中的字符进行比较，首先将字符串P从第0个位置起与主串T的第pos个字符起依次进行比较对应字符，如果全部对应相等，则表明已找到匹配，成功终止；否则将字符串P从第0个位置起与主串T的第pos+1个字符起依次进行比较对应字符，过程类似。如果直到匹配完主串T的所有字母都没有找到，...

算法之截取带汉字的字符串【代码】

输入“我ABC汉DEF”和字节数6，应该输出“我ABC”，而不是“我ABC+汉的半个”。publicclass CutOutHanzi {publicstaticvoid main(String[] args) throws UnsupportedEncodingException {String str = "我ABC汉DEF";cutOutGBK(str,6);}publicstatic String cutOutGBK(String str,int n) throws UnsupportedEncodingException{//n为要截取的字节数byte[] buf = str.getBytes("GBK");int num = 0;boolean isHanziFirstHalf = false;fo...

算法训练字符串逆序【代码】

算法训练字符串逆序时间限制：1.0s 内存限制：512.0MB 　　输入一个字符串，长度在100以内，按相反次序输出其中的所有字符。样例输入tsinghua样例输出auhgnistimport java.util.Scanner; publicclass Main {publicstaticvoid main(String[] args) {// TODO Auto-generated method stubScanner sc=new Scanner(System.in);String s=sc.nextLine();char a[]=s.toCharArray();for(int i=a.length-1;i>=0;i--){System.out.prin...

c数据结构的字符串查找的Brute-Force算法

#include<stdio.h> #include<malloc.h> #include<string.h> //定义字符串的结构体 typedef struct {char *str;//字符串int maxLength;//最大可以存放字符的长度int length;//目前的字符长度 }DString; //1.初始化操作 //初始化操作用来建立和存储串的动态数组空间以及给相关的数据域赋值 void Initiate(DString *s,int max,char *string){int i;s->str=(char *)malloc(sizeof(char)*max);//申请动态存储空间s->maxLength=max;//动态...

字符串与模式匹配算法（五）：BMH算法【代码】

一、BMH算法介绍在BM算法的实际应用中，坏字符偏移函数的应用次数要远远超过好后缀偏移函数的应用次数，坏字符偏移函数在匹配过程中起着移动指针的主导作用。在实际匹配过程，只是用坏字符偏移函数也非常有效。1980年，奈杰尔·豪斯普（Nigel Horspool）提出了改进的BM算法，也就是BMH算法。简化了BM算法，执行非常方便，效率也很可观。Boyer-Moore算法使用两种策略来确定不匹配模式的位移：坏字符策略和高端策略。来自Horspool的想...

算法基础：删除字符串中出现次数最少的字符（Golang实现）

描写叙述: 实现删除字符串中出现次数最少的字符。若多个字符出现次数一样，则都删除。输出删除这些单词后的字符串。字符串中其他字符保持原来的顺序。输入: 字符串仅仅包括小写英文字母, 不考虑非法输入，输入的字符串长度小于等于20个字节。输出: 删除字符串中出现次数最少的字符后的字符串。例子输入: abcdd 例子输出: dd代码实现package huaweiimport ("fmt" )func Test4Base() {s := "abcfbcca"result := deleteMinChars(s...

字符串与模式匹配算法（三）：KMP算法【代码】【图】

一、KMP算法介绍　　KMP算法与前面的MP算法一脉相承，都是充分利用先前匹配的过程中已经得到的结果来避免频繁回溯。回顾一下MP算法，如下图的模式串偏移，当前模式字符串P的左端的p0与目标字符串T中tj位置对齐。从左向右逐个进行比较，发现 pi 处的字符a 与 tj+1 处字符b发生失配。同时也表明 P(p0,p1,...,pi-1) 与 T‘(tj,tj+1,...,tj+i-1) 是完全匹配的，这一部分子串在图中用字母u标示出。由于发生失配，随即移动模式字符串并进...

字符串查找算法-KMP

/** * KMP algorithm is a famous way to find a substring from a text. To understand its‘ capacity, we should acquaint onself with the normal algorithm.*//** * simple algorithm * * workflow: * (say, @ct means for currently position of search text) * * step 1: match text from index @ct with pattern. * step 2: if success, step to next character. or, * * The most...

今天面试问了一道题。说一串字符串由这几个符号组成"<>{}[]()”,写一个算法，例如如果组成方式为“<>{[]}{}()”这种，也就是XML格式那种则返回true。否则返回false；【代码】【图】

原创今天面试问了一道题。说一串字符串由这几个符号组成"<>{}[]()”,写一个算法，例如如果组成方式为“<>{[]}{}()”这种，也就是XML格式那种则返回true。否则返回false；当时没想出来，只想到了回文数解决办法。回文数解决办法是颠倒比较，相等为true；换xml格式当时真没想到啥好方法；在回来的路上想到了。。。。去重，吧临近的一组去掉，在递归调用比较去重直到最后，如果有剩下则不返回false；否则true；代码为package hao;imp...

编程算法 - 把字符串转换为整数代码(C)【图】

把字符串转换为整数代码(C)本文地址: http://blog.csdn.net/caroline_wendy题目: 写一个函数StrToInt, 模拟atoi的功能, 把字符串转换为整数.须要考虑异常处理, 正负数, 还有Int的最大值(0x7FFFFFFF)和最小值(0x80000000)等情况.代码:/** main.cpp** Created on: 2014.7.12* Author: spike*/#include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h>enum Status {kValid=0, kInvalid};int g_nStatus =...

数据结构——算法之（028）（寻找当中的一个子字符串个数）

【申明：本文仅限于自我归纳总结和相互交流，有纰漏还望各位指出。联系邮箱：Mr_chenping@163.com】题目：已知一个字符串,比方asderwsde,寻找当中的一个子字符串比方sde 的个数,假设没有返回0,有的话返回子字符串的个数题目分析：1、顺序遍历字符串，然后用strncmp比較就可以算法实现：#include <stdio.h> #include <string.h>int sub_str_count(const char *str, const char *sub_str) {int str_len = strlen(str);int sub_str_l...

【字符串处理算法】字符串包含的算法设计及C代码实现【图】

一、需求描述给定一个长字符串和一个短字符串，编写程序判断短字符串中的所有字符是否都在长字符串中。如果是，则长字符串包含短字符串；反之，不包含。为了尽量包含大多数情况，字符串中可以包含大小写英文字母、数字和各种标点符号，并且区分大小写字母。下面举几个例子予以说明：1.如果长字符串是“ABCDE”，短字符串是“ADC”，那么短字符串中的所有字符都在长字符串中，即长字符串包含了短字符串。2.如果长字符串是“ABCDE”，...

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法

内容导读

内容图文

常见字符串问题:

KMP算法：

Boyer-Moore算法

Manacher算法：

AC自动机:

双数组trie:

后缀自动机：

References:

内容总结

内容备注

内容手机端

【字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法】教程文章相关的互联网学习教程文章

字符串数据结构算法题-C++【代码】

103-算法应用【字符串反转】代码实现【代码】

字符串模式匹配算法2 - AC算法【代码】【图】

字符串匹配算法（在字符串T中查找是否有与字符串P相同的子串）

算法之截取带汉字的字符串【代码】

算法训练字符串逆序【代码】

c数据结构的字符串查找的Brute-Force算法

字符串与模式匹配算法（五）：BMH算法【代码】

算法基础：删除字符串中出现次数最少的字符（Golang实现）

字符串与模式匹配算法（三）：KMP算法【代码】【图】

字符串查找算法-KMP

今天面试问了一道题。说一串字符串由这几个符号组成"<>{}[]()”,写一个算法，例如如果组成方式为“<>{[]}{}()”这种，也就是XML格式那种则返回true。否则返回false；【代码】【图】

编程算法 - 把字符串转换为整数代码(C)【图】

数据结构——算法之（028）（寻找当中的一个子字符串个数）

【字符串处理算法】字符串包含的算法设计及C代码实现【图】

字符串 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程

首页 / 算法 / 字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法 后缀树算法

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法 后缀树算法

内容导读

内容图文

常见字符串问题:

KMP算法：

Boyer-Moore算法

Manacher算法：

AC自动机:

双数组trie:

后缀自动机：

References:

内容总结

内容备注

内容手机端

【字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法 后缀树算法】教程文章相关的互联网学习教程文章

字符串 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程

首页 / 算法 / 字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法

字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法

【字符串四大经典算法 Knuth-Morris-Pratt Boyer-Moore AC(Aho-Corasick)算法后缀树算法】教程文章相关的互联网学习教程文章