精华内容
下载资源
问答
  • 本篇是对于KMP单模式匹配以及AC算法多模式匹配的简单讲解,KMP算法与AC算法是关键字检索中的常见算法,能够快速而高效地查找出目标字符串中的个关键字的匹配情况,而要检索的关键字通常被称为模式串,因此模式匹配...

    前言

    本篇是对于KMP单模式匹配以及AC算法多模式匹配的简单讲解,KMP算法与AC算法是关键字检索中的常见算法,能够快速而高效地查找出目标字符串中的多个关键字的匹配情况,而要检索的关键字通常被称为模式串,因此模式匹配四个字也就好理解了。网上的很多对于KMP的讲解总是结合了很多的数学公式,很多的晦涩难懂的专业词语,让人看了很头大,至少对于蠢笨的我来说,实在是一场煎熬,因此本篇的说明尽量做到通俗易懂,从逻辑以及思考方式的角度来对模式匹配的算法进行讲解。

     

    一、KMP单模式匹配算法

    1、综述

    在描述多模式匹配算法之前,对于单模式匹配先进行一个简单的描述。单模式匹配与多模式匹配的不同点在于单模式匹配是搜索一个关键字,多模式匹配是搜索多个关键字。

             单模式匹配解决的是在长度为m的目标串(一个长字符串L)中查找长度为n的模式串(短字符串S)的问题,如果按照最粗糙的方法暴力求解,代码应该是这样的:

             for(inti=0; i<m; i++){

                       for(intj=0; j<n; j++){

                                //依次比较L[i] 与S[j],当完全相等的情况下记录

    }

    }

    嗯,很不错的代码,思路清晰,结构明确,就是太慢了,时间代价为O(m*n)。于是情不自禁地想要快一点,这里就请出了KMP,KMP的核心思想就是比过的字符串就不比了,为了实现这一句话,KMP在模式串的基础上,加入了next表来进行实现。

    因此KMP中需要说明的就是两点,一点是next表,另一点就是对比的方式(与暴力解法的区别在哪)。

    2、next表

    之前的描述中,KMP的核心在于六个大字:比过的,不比了。那么这个实现的方式就是通过next表。这里先举一个简单的模式串对应next表的例子:

    j

    1

    2

    3

    4

    5

    6

    7

    pattern

    a

    b

    c

    a

    b

    c

    d

    next

    0

    1

    1

    1

    2

    3

    4

             好的,这样一个表格的含义是什么呢,来猜一猜。首先是j,j的值从1-7,嗯,那就是编号?其次是pattern,pattern的意思是模式,那这个就是要检索的模式串了?接下来是next,好像之前提到了next表,那就可以大胆预测next就代表了next表!

             那么我猜对了吗?恭喜我自己,答对了!(好高兴)

             那好,既然每一行的名称的意义弄清楚了,接下来就是每一行的作用,第一行的j的作用很明确,就是编号,有一点要注意的是这里的编号的起始是1开始的而不是0。第二行的pattern是模式串,那就说明我们的模式串就是abcabcd。第三行的next代表的是next表,接下来要讲的就是它。

             讲next之前,先回忆一下暴力求解的时候,我们的流程是什么,先来一个目标串(要被检索的长字符串)abcdbcaaad,我们的模式串是abcabcd,这样首先从两个字符串的开始位置依次对比,当对比到第四个字符的时候,目标串的’d’与模式串的’a’不同,于是需要继续对比,将模式串adbadcd向后移动一位,将模式串的’a’与目标串的第二个字符’b’又开始对比,这样依次类推。这样做是完全正确的,思路清晰目标明确,只是太慢了而已,而慢的原因就在于每次对比失败时,模式串都只是向后移动一格,造成了很多重复的对比,无法实现“比过了不比了”这一伟大的宏观战略目标,为了解决这个问题,经典的KMP算法就出现了。

             那么现在看来next表确实非常关键,它能够实现我们“比过了不比了”这个伟大的目标。首先是讲一讲next表当中各个数字的含义和作用,例子当中的next表的值为0001230,其中每一个数字的含义是:当前字符之前的子字符串片段,从前向后数与从后往前数,能够相等的子字符串的最大长度加一。额,好像依然不能令人清晰它的含义,那接下来还是用几个例子来说明:对于字符串abcab的子字符串abca,从前往后数,可以得到a,ab,abc,从后往前数,可以得到a,ca,bca,明显可以看出来,最大的相等的子字符串就是a,长度为1,因此abcab的next值就应该为1+1=2,其实一眼也可以看出来,从前往后数最大也就有一个a和后面的a相等,就可以得到next值为2;再举一个例子,abc的子字符串ab,从前往后数有a,从后往前数有b,就是一个相等的都没有,那么就是它的next值就是0+1=1。所以到这里应该已经懂了,就重新说一遍之前的话:当前字符之前的子字符串片段,从前向后数与从后往前数,能够相等的子字符串的最大长度加一。这样的话,next表的每一个数值的含义与计算方法就已经明确了,接下来就是它的作用。

             重复地再说一次,next表的作用是“比过了不比了”,那么他每一个数字的作用就是记录了实现这一目标的方法。与传统的暴力解法不一样,当KMP遭遇到对比不一致的情况时,KMP不是简单地向后移动一格继续对比,而是将向后移动(j-next[j])的距离。依然以一个例子来说明,目标字符串是abadbcaaad,模式串为abcabcd,暴力解法中,对比到目标串的第三个字符时发现不一样,于是又从目标串的第二位开始对比。这里就是可以思考的地方了:既然目标字符串的aba已经和模式串的abc进行过对比了,那我们是不是就可以不比了呢?答案是肯定的,而不比了的含义就是,可以直接将模式串abcabcd移动到目标串的第四位’d’的位置(3-next[3]=3,移动3格)开始匹配对比。那这样突然就感觉很棒了,不再一个一个的进行对比,能够一次性地跨越已经比过的位置,但是并不是所有的目标串都是可以直接跳过所有已经对比的子字符串的,还需要考虑下面的这种情况:一个新的例子,目标串为abcabcabcd,模式串为abcabcd,首次对比中,对比到目标串的第7个字符’a’时发现了不一样,但是这里的移动如果直接移动到目标串第八位的位置’b’开始比较,明显就会错过abc(abcabcd)中括号括起来的部分,所以这里的移动是移动到目标串的第四个字符’a’的位置(7-next[7]=3,移动3格)进行对比。

    3、总结

             OK,讲到这里next表的含义和使用方法也算是讲完了,而KMP算法也就主要实现了两点,其一是通过比过了不比了的思想直接跳过大段的字符串,另一个是通过next表确认当前字符前的重复数量来避免跳过过多的字符串。

             好了,今天就到这里了,搞定收工!

    (最后说明一下,在网上与书中的资料中,j与next的数值的计算方法都有些微的差异,但是根本的目的都是在于记录j字符之前的子串的前后缀最大匹配数值,本文重在将模式匹配的逻辑与思考方式描述,不讨论具体细节。)

    展开全文
  • 字符串匹配(多模式匹配篇)

    千次阅读 2018-05-12 22:39:22
    字符串匹配(多模式匹配篇)摘要:问题的提出:众所周知,KMP算法在O(n)的时间中solve单模式串匹配问题。但怎样solve模式串匹配问题呢?Solve:本文用简要记叙了使用trie树,trie图(AC自动机)solve该问题的...

    字符串匹配(多模式匹配篇)

    摘要:

    问题的提出:众所周知,KMP算法在O(n)的时间中solve单模式串匹配问题。但怎样solve多模式串匹配问题呢?

    Solve:本文用简要记叙了使用trie树,trie图(AC自动机)solve该问题的方法。

    关键字:

    字符串,多模式串匹配,trie树,trie图,AC自动机。

    前言:

    KMP算法是一种极其优秀的单模式串匹配算法,它通过前缀函数fail来减少匹配次数,以达到O(n)的单串匹配。但当KMP算法用于解决多模式串匹配问题时,时间复杂度为O(nq),十分低效。

    因此,我们去探索一些更适合于多模式串匹配问题的算法用以解决这个问题。

    第1节主要介绍trie树。

    第2节主要介绍trie图。

    第三节给出一些例题。

    1.trie树

    1.0问题的引入:

           给定一个原串s,n个模式串st[i],求st[i]是否出现在s中。

    1.1字典树的定义:


    又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

    ——来源于百度百科

    1.2字典树的性质:

         根节点不包含字符,除根节点外每一个节点都只包含一个字符; 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串; 每个节点的所有子节点包含的字符都不相同。

         每一个节点u都包含next[v],value。

         next[v]表示节点u的v边指向的节点编号。

         value表示危险节点所属的模式串编号,若value=0表示这不是一个危险节点。

         根节点表示空串。

         这样一棵trie树的深度为O(max(len)+1)

         可以发现当且仅当s1是s2的前缀,那么在trie树上,s2的路径是包含s1的路径的。

             

    1.2字典树的实现:

    字典树的操作是十分简单的(建议读者根据性质自己推导实现过程)。

    插入:

    void build_trie_tree(char *st,int len,int p)
    {
    	int x=1;
    	for (int i=0;i<len;i++)
    	{
    		if (trie[x].next[st[i]]==0)       //若该边不存在,新建点和边。
    		{
    			nodenum++;
    			trie[x].next[st[i]]=nodenum;
    		}
    		x=trie[x].next[st[i]];            //跳转至下一个节点。
    	}
    	trie[x].value=p;                               //标记是否为危险节点。
    }

    (删除一个子树的操作不再叙述,基本思想是增加一个tag懒标记,表示此节点及其子树被删除。)

    查询(查询某一字符串是否在trie树中):

    bool query_trie_tree(char *st,int len)
    {
    	int x=1;
    	for (int i=0;i<len;i++) x=trie[x].next[st[i]];   //跳转至目标节点
    	if (!trie[x].value) return 1;
    }

    查询2(多串查询):

    我们只需要枚举起始位置i,寻找st[i->j](i<=j<=len)是否出现即可。

    void query_trie_tree(char *st,int k,int len)
    {
    	int x=1;
    	for (int i=k;i<len;i++)
    	{
    	    x=trie[x].next[st[i]];                    //跳转 
    	    if (x) return;                            //匹配失败退出 
    	    if (trie[x].value) fst[trie[x].value]=k;  //fst[i]记录i模式串出现在原串中的起始位置 
    	}
    }
    void work(char *st,int len)
    {
    	for (int i=0;i<len;i++)
    	    query_trie_tree(st,i,len);             //枚举所有起点位置 
    }


    1.4trie树的分析:(注:下文中|SIGMA|表示字符集大小,而sigma表示求和函数)

    构造出trie树的结构,构造时间是O(sigma(len)),单串匹配的时间复杂度很明显是O(len)级别的。

    多串匹配需要枚举原串的起始点u,再从trie树中查询,时间为O(lens*max(len))

    比起这个,更让我们关心的是空间复杂度,O(|SIGMA|n)。倘若空间不足,可以将next[v]用边表的形式记录下来,或者用左儿子,右兄弟的方法记录。

    这样的数据结构无论从时间或是空间上都和KMP相差无几,但更加形象具体了。那么如何改变这个数据结构使它能够完成多串匹配任务呢?


    注:将trie树从上到下,从左到右标号,根为1


    我们发现在trie树上多串匹配,会产生许多浪费。

    比如模式串为ab。

    以上图中的trie树来匹配,跳转顺序是

    1->2->5(ab)

    1->3(b)

    而匹配ab时已经将b匹配了一遍,但在做完ab之后却返回了根,重新匹配了b,得不偿失。

    所以想要优化trie树,就要使每一次精确跳转到最有效的位置。

    进入到trie图时代。


    2.trie图

    2.0trie图的引入——解决上述问题:

    什么是精确跳转呢?


    在这个图中,abc的精确跳转应该是bc。

    abd的精确跳转为根(空串)

    字符串s的精确跳转节点是trie树中存在的s最长的后缀,称为后缀fail。

    2.1trie图的概念:

    在trie树上添加前缀指针fail并补齐trie树的边,所构造的图。

    2.2trie图的性质:

    trie图的目的是让每一次都精确地跳转。

            

            如该图中的的fail应该指向bc。

           节点u的fail应该为u的父亲节点的fail点的该边。(fail[u]=trie[father[fail[u]]].next[ch])

           读者可以计算一下当trie图中只有单串的时候,fail和KMP的next两个数组有什么特殊的联系。

           能够很轻易地看出:若trie图按0开始编号,next[i]=fail[i]

    2.3trie图的实现:(建议读者自行思考后对照)

       构造trie图:

    void build_trie_graph()
    { 
    	trie[1].fail=1;                            //根的后缀为根
    	for (int i=1;i<=p;i++)
    	if (trie[1].next[i]) 
    	{
    		trie[trie[1].next[i]].fail=1;
    		que.push(trie[1].next[i]);
    	}                                          //根的儿子的后缀为根
    	else trie[1].next[i]=1;                    //根的新边为根
    	
    	while (!que.empty())
    	{
    		int q=que.front();
    		que.pop();
    		for (int i=1;i<=p;i++)
    		{
    			int v=trie[q].next[i];
    			if (v)
    			{
    				trie[v].fail=trie[trie[q].fail].next[i];
    				que.push(v);
    			}
    			else trie[q].next[i]=trie[trie[q].fail].next[i];
    		}
    		if (trie[trie[q].fail].value) trie[q].value=trie[trie[q].fail].value;
    	}
    }

    遍历:

    void query_trie_tree(char *st,int len)
    {
    	int x=1;
    	for (int i=0;i<len;i++) 
    	{ 
    	    if (!trie[x].value) solve_probleam();
    		x=trie[x].next[st[i]];   //跳转至目标节点
    	}
    }


    3.来几道例题练练手!

    3.1  Video Game

    Bessie is playing a video game! In the game, the three letters 'A', 'B',

    and 'C' are the only valid buttons. Bessie may press the buttons in any
    order she likes; however, there are only N distinct combos possible (1 <= N
    <= 20). Combo i is represented as a string S_i which has a length between 1
    and 15 and contains only the letters 'A', 'B', and 'C'.

    Whenever Bessie presses a combination of letters that matches with a combo,
    she gets one point for the combo. Combos may overlap with each other or
    even finish at the same time! For example if N = 3 and the three possible
    combos are "ABA", "CB", and "ABACB", and Bessie presses "ABACB", she will
    end with 3 points. Bessie may score points for a single combo more than once.

    Bessie of course wants to earn points as quickly as possible. If she
    presses exactly K buttons (1 <= K <= 1,000), what is the maximum number of
    points she can earn?

    给你个模式串(每个长度≤15,1≤N≤20),串中只含有“ABC”三种字母。求一长度为K(1≤K≤1000)的字符串,使得匹配数最大(重复匹配计多次),输出最大值。

    题解:先构造trie图,然后动态规划。

    f[step][u]表示第step步走到u点经过的最多危险节点数量。

    f[step+1][trie[u].next[k]]=max{f[step+1][trie[u].next[k]],f[step[u]+trie[trie[u].next[k]].value }

    #include<bits/stdc++.h>
    using namespace std;
    const int MAXANS=10000000;
    struct node
    {
        int ch[5],fail,value;
    } trie[505];
    int nodenum=1,n,m;
    int f[1005][505];
    char st[25];
    queue<int> que;
    int smax(int x,int y){return x>y?x:y;}
    void build_trie_tree(char *st,int len)
    {
        int u=1;
        for (int i=0;i<len;i++)
        {
            if (!trie[u].ch[st[i]-64])
            {
                nodenum++;
                trie[u].ch[st[i]-64]=nodenum;
            }
            u=trie[u].ch[st[i]-64];
        }
        trie[u].value++;
    }
    void build_trie_graph()
    {
        trie[1].fail=1;
        for (int i=1;i<=3;i++)
            if (trie[1].ch[i])
            {
                trie[trie[1].ch[i]].fail=1;
                que.push(trie[1].ch[i]);
            }
            else trie[1].ch[i]=1;
        while (!que.empty())
        {
            int u=que.front();
            que.pop();
            for (int i=1;i<=3;i++)
            if (trie[u].ch[i])
            {
                trie[trie[u].ch[i]].fail=trie[trie[u].fail].ch[i];
                que.push(trie[u].ch[i]);
            }
            else trie[u].ch[i]=trie[trie[u].fail].ch[i];
            if (trie[trie[u].fail].value) 
                trie[u].value+=trie[trie[u].fail].value;
        }
    }
    void solve()
    {
        for (int step=0;step<=m;step++)
            for (int i=1;i<=nodenum;i++)
            f[step][i]=-MAXANS;
        f[0][1]=0;
        for (int step=0;step<m;step++)
            for (int i=1;i<=nodenum;i++)
                for (int j=1;j<=3;j++)
                {
                    int v=trie[i].ch[j];
                    f[step+1][v]=smax(f[step+1][v],f[step][i]+trie[v].value);
                }
        int ans=0;
        for (int i=2;i<=nodenum;i++) ans=smax(ans,f[m][i]); 
        printf("%d\n",ans); 
    }
    int main()
    {
        scanf("%d%d",&n,&m);
        for (int i=1;i<=n;i++)
        {
            scanf("%s",st);
            build_trie_tree(st,strlen(st));
        }
        build_trie_graph();
        solve();
        return 0;
    }
    

    OJ上实测速度很快。只用了20MS(rank1膨胀逃)。


    3.2阿狸的打字机

    BZOJ2434 阿狸的打字机
    阿狸喜欢收藏各种稀奇古怪的东西,最近他淘到一台老式的打字机。打字机上只有28个按键,分别印有26个小写英文字母和’B’、’P’两个字母。 
    经阿狸研究发现,这个打字机是这样工作的: 
    ·输入小写字母,打字机的一个凹槽中会加入这个字母(这个字母加在凹槽的最后)。 
    ·按一下印有’B’的按键,打字机凹槽中最后一个字母会消失。 
    ·按一下印有’P’的按键,打字机会在纸上打印出凹槽中现有的所有字母并换行,但凹槽中的字母不会消失。 
    例如,阿狸输入aPaPBbP,纸上被打印的字符如下: 

    aa 
    ab 
    我们把纸上打印出来的字符串从1开始顺序编号,一直到n。打字机有一个非常有趣的功能,在打字机中暗藏一个带数字的小键盘,在小键盘上输入两个数(x,y)(其中1≤x,y≤n),打字机会显示第x个打印的字符串在第y个打印的字符串中出现了多少次。 
    阿狸发现了这个功能以后很兴奋,他想写个程序完成同样的功能,你能帮助他么?
    Input
    输入的第一行包含一个字符串,按阿狸的输入顺序给出所有阿狸输入的字符。
    第二行包含一个整数m,表示询问个数。
    接下来m行描述所有由小键盘输入的询问。其中第i行包含两个整数x, y,表示第i个询问为(x, y)。
    Output
    输出m行,其中第i行包含一个整数,表示第i个询问的答案。
    Sample Input
    aPaPBbP
    3
    1 2
    1 3
    2 3
    Sample Output 
    2
    1
    0
    Hint
    1<=N<=10^5
    1<=M<=10^5
    输入总长<=10^5

    明显的trie图。

    不解释,大佬们都会的。

    noi压轴题原来这么简单!!!(逃))



    3.3宇宙队神题!

    题目受宇宙队管制,暂时无法查看。


    3.4经典好题!

    POJ 1204 Word Puzzles

    POJ 1625 Censored! 

    POJ 2778 DNA Sequence 

    HDU 2457 DNA repair

    ural 1269. Obscene Words Filter

    [BZOJ1195][HNOI2006]最短母串


    4.总结

    trie树,trie图还是属于简单易写的匹配算法。

    trie树,trie图一般用于解决三种问题:

    1.多个字符串的存储。

    2.多个字符串的匹配、查询、字符串树(图)上操作。

    3.辅助其他算法(如DP等)存取数据。

    大家有时间可以对比一下KMP和trie图的其他性质的相同点。

    trie


    展开全文
  • 字符串多模式匹配:AC算法

    万次阅读 2017-03-21 19:17:22
    早在1975年贝尔实验室的两位研究人员Alfred V. Aho 和Margaret J. Corasick就提出了以他们的名字... AC算法是一个经典的多模式匹配算法,可以保证对于给定的长度为n的文本,和模式集合P{p1,p2,…pm},在O(n)时间复杂度

      早在1975年贝尔实验室的两位研究人员Alfred V. Aho 和Margaret J. Corasick就提出了以他们的名字命名的高效的匹配算法—AC算法。该算法几乎与《KMP算法》同时问世。与KMP算法相同,AC算法时至今日仍然在模式匹配领域被广泛应用。
      
      AC算法是一个经典的多模式匹配算法,可以保证对于给定的长度为n的文本,和模式集合P{p1,p2,…pm},在O(n)时间复杂度内,找到文本中的所有目标模式,而与模式集合的规模m无关。
      
      正如KMP算法在单模式匹配方面的突出贡献一样,AC算法对于多模式匹配算法后续的发展也产生了深远的影响,而且更为重要的是,两者都是在对同一问题——模式串前缀的自包含问题的研究中,产生出来的,AC算法从某种程度上可以说是KMP算法在多模式环境下的扩展。
      
      如果要用KMP算法匹配长度为n的文本中的m个模式,则需要为每一个模式维护一个next跳转表,在执行对文本的匹配过程中,我们需要关注所有这些next表的状态转移情况,这使得时间复杂度增长为O(mn),对于较大的模式集合来说,这样的时间增长可能是无法接受的。AC算法解决了这一问题,通过对模式集合P的预处理,去除了模式集合的规模对匹配算法速度的影响。
      

    AC定义:

    AC有限自动机 M 是1个6元组:M =(Q,∑,g,f,qo,F)其中:

    1、Q是有限状态集(模式树上的所有节点).
    2、∑是有限的输入字符表(模式树所有边上的字符).
    3、g是转移函数.
    4、f是失效函数,不匹配时自动机的状态转移.
    5、qo∈Q是初态(根节点);
    6、F量Q是终态集(以模式为标签的节点集).

    AC算法思想

      多模式匹配AC算法的核心仍然是寻找模式串内部规律,达到在每次失配时的高效跳转。这一点与单模式匹配KMP算法和BM算法是一致的。不同的是,AC算法寻找的是模式串之间的相同前缀关系。
      
      要理解AC算法,仍然需要对KMP算法的透彻理解。那么前缀自包含如何在AC算法中发挥作用?
      
      在KMP算法中,对于模式串”abcabcacab”,我们知道非前缀子串abc(abca)cab是模式串的一个前缀(abca)bcacab,而非前缀子串ab(cabca)cab不是模式串abcabcacab的前缀,根据此点,我们构造了next结构,实现在匹配失败时的跳转。
      
      而在多模式环境中,这个情况会发生一定的变化。
      对于模式集合P{he,she,his,hers},模式s(he)的非前缀子串he,实际上却是模式(he),(he)rs的前缀。如果目标串target[i…i+2]与模式she匹配,同时也意味着target[i+1…i+2]与he,hers这两个模式的头两个字符匹配,所以此时对于target[i+3],我们不需要回溯目标串的当前位置,而直接将其与he,hers两个模式的第3个字符对齐,然后直接向后继续执行匹配操作
      
      经典的AC算法由三部分构成,goto表,fail表和output表,共包含四种具体的算法,分别是计算三张查找表的算法以及AC算法本身。
      goto表是由模式集合P中的所有模式构成的状态转移自动机。
      failure表作用是在goto表中匹配失败后状态跳转的依据,这点与KMP中next表的作用相似。
      output表示输出,又称:emits,即代表到达某个状态后某个模式串匹配成功

    构造goto表

      goto表是由模式集合P中的所有模式构成的状态转移自动机,本质上是一个有限状态机,这里称作模式匹配机(Pattern Matching Machine,PMM)。
      
      对于给定的集合P{p1,p2,…pm},构建goto表的步骤是,对于P中的每一个模式pi[1…j](1 <= i < m+1)),按照其包含的字母从前到后依次输入自动机,起始状态D[0],如果自动机的当前状态D[p],对于pi中的当前字母pi[k](1<=k<=j),没有可用的转移,则将状态机的总状态数smax+1,并将当前状态输入pi[k]后的转移位置,置为D[p][pi[k]] = smax,如果存在可用的转移方案D[p][pi[k]]=q,则转移到状态D[q],同时取出模式串的下一个字母pi[k+1],继续进行上面的判断过程。这里我们所说的没有可用的转移方案,等同于转移到状态机D的初始状态D[0],即对于自动机状态D[p],输入字符pi[k],有D[p][pi[k]]=0。
      
      对于模式集合P{he,she,his,hers}, goto表的构建过程如下:
      
      1、PMM初始状态为0,然后向PMM中加入第一个模式串K[0] = “he”。
      
        
      
      2、继续向PMM中添加第二个模式串K[1] = “she”,每次添加都是从状态0开始扫描。
      
        
      
      3、从状态0开始继续添加第三个模式串K[2] = “his”,这里值得注意的是遇到相同字符跳转时要重复利用以前已经生成的跳转。如这里的’h’在第一步中已经存在。
      
        
      
      4、添加模式串K[3] = “hers”。至此,goto表已经构造完成。
      
        

      对于第一和第二步而言,两个模式没有重叠的前缀部分,所以每输入一个字符,都对应一个新状态。第三步时,我们发现,D[0][p3[1]]=D[0][‘h’]=1,所以对于新模式p3的首字母’h’,我们不需要新增加一个状态,而只需将D的当前状态转移到D[1]即可。而对于模式p4其前两个字符he使状态机转移至状态D[2],所以其第三字符对应的状态D[8]就紧跟在D[2]之后。

    构造failure表

      failure表作用是在goto表中匹配失败后状态跳转的依据,这点与KMP中next表的作用相似。
      
      首先说明什么状态,在上面goto表的图里,把圆圈里的数字记为状态。
      
      再引入状态深度的概念,状态s的深度depth(s)定义为在goto表中从起始状态0到状态s的最短路径长度。如goto表中状态1和3的深度为1。
      
      计算思路:先计算所有深度是1的状态的失效函数值,然后计算所有深度为2的状态,以此类推,直到所有状态(除了状态0,因为它的失效函数没有定义)的失效函数值都被计算出。

      计算方法:用于计算某个状态失效函数值的算法在概念上是非常简单的。首先,令所有深度为1的状态s的函数值为f(s) = 0。假设所有深度小于d的状态的f值都已经被算出了,那么深度为d的状态的失效函数值将根据深度小于d的状态的失效函数值来计算。
     
      具体步骤: 构造failure表利用到了递归的思想。

    1、若depth(s) = 1,则f(s) = 0;即与状态0距离为1(即深度为1)的所有状态的fail值都为0
    2、假设深度为d-1的所有状态r, 即depth(r) < d,已经计算出了f(r);
    3、那么对于深度为d的状态s:
      (1) 若所有的字符a, 满足g(r,a) = fail,则不动作;(注:g为状态转移函数)
      (2) 否则,对每个使 g(r, a) = s成立的字符a,执行以下操作::
         a、使state = f(r)
         b、重复步骤state = f(state),直到g(state, a) != fail。(注意对于任意的a,状态0的g(0,a) != fail)
         c、使f(s) = g(state, a)。

      例子: 求状态4 的failure 状态,已知其前一个(父节点)的f(1)= 0,且状态0(根节点)有字符’h’的外向边,该外向边对应状态1,则有f(4) = 1;类似前缀规则:求已经匹配字串”sh” 最大后缀,同时是某个模式串的前缀;

      根据以上算法,得到该例子的failure表为:
      i  1  2  3   4   5  6  7  8  9
      f(i) 0  0  0   1   2  0  3  0  3
       
      将failure表用虚线表现,整合goto表,得到下图:
        

    构造output表

      output表示输出,即代表到达某个状态后某个模式串匹配成功。该表的构造过程融合在goto表和failure表的构造过程中。
      
       1、在构造goto表时,每个模式串结束的状态都加入到output表中,也就goto表中的黑色加粗圆圈。得到
         i    output(i)
         2   {he}
         5   {she}
         7   {his}
         9   {hers}
       2、在构造failure表时,若f(s) = s’,则将s和s‘对应的output集合求并集。如f(5) = 2,则得到最终的output表为:
          i   output(i)
          2   {he}
          5   {she,he}
          7   {his}
          9   {hers}

    AC算法匹配过程

    这里写图片描述
      
       自动机从根节点0出发
       1、首先尝试按success表转移(图中实线)。按照文本的指示转移,也就是接收一个u。此时success表中并没有相应路线,转移失败。
       2、失败了则按照failure表回去(图中虚线)。按照文本指示,这次接收一个s,转移到状态3。
       3、成功了继续按success表转移,直到失败跳转步骤2,或者遇到output表中标明的“可输出状态”(图中红色状态)。此时输出匹配到的模式串,然后将此状态视作普通的状态继续转移。

       根据上面已经构造好的goto、failure和output表。以字符串”ushers”为例。状态转移如下:
            u   s   h   e   r   s
         0  0   3   4  5  8   9
                        2
       说明:在状态5发生失配,查找failure表,转到状态2继续比较。在状态5和状态9有输出。
      
       算法高效之处在于,当自动机接受了“ushe”之后,再接受一个r会导致无法按照success表转移,此时自动机会聪明地按照failure表转移到2号状态,并经过几次转移后输出“hers”。来到2号状态的路不止一条,从根节点一路往下,“h→e”也可以到达。而这个“he”恰好是“ushe”的结尾,状态机就仿佛是压根就没失败过(没有接受r),也没有接受过中间的字符“us”,直接就从初始状态按照“he”的路径走过来一样(到达同一节点,状态完全相同)。

    AC算法具体实现:

    robert-bor实现的ac算法(java):https://github.com/robert-bor/aho-corasick
    hankcs改进robert-bor的ac算法(java):https://github.com/hankcs/aho-corasick

    简单实现java:

    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.Collections;
    import java.util.Hashtable;
    import java.util.List;
    
    public class ACTest {
    
        static String Text = "ushers";
        static String[] Pattens = {"he", "she", "his", "hers"};
        // 根节点
        static TreeNode root; 
    
        public static void main(String[] args) {
            buildGotoTree(); // 构建goto表和output表
            addFailure();    // 构建failure表
            printTree();     // 打印tree的字符、深度、状态,fail值
            acSearch();      // 查找ushers, 并打印匹配的位置和模式
        }
    
        /**
         * 构建Goto表和output表
         */
        public static void buildGotoTree(){
            int i = 1;
            root = new TreeNode(null, ' ');
            // 判断节点是否存在, 存在转移 ,不存在添加   
            for (String word : Pattens) { 
                TreeNode temp = root;
                for (char ch : word.toCharArray()) {  
                    TreeNode innerTem = temp.getSonNode(ch);
                    if(innerTem == null){
                        TreeNode newNode = new TreeNode(temp, ch); 
                        newNode.setStatus(i++);
                        temp.addSonNode(newNode);  
                        innerTem = newNode;  
                    }
                    temp = innerTem;
                }  
                temp.addResult(word);
            }  
        }
    
        /**
         * 构建failure表
         * 遍历所有节点, 设置失败节点 原则: 节点的失败指针在父节点的失败指针的子节点中查找 最大后缀匹
         */
        public static void addFailure(){
            // 过程容器  
            ArrayList<TreeNode> mid = new ArrayList<TreeNode>();
    
            // 首先,设置二层失败指针为根节点 收集三层节点。 即令所有深度为1的状态s的函数值为f(s) = 0。 
            for (TreeNode node : root.getSons()) {  
                node.setFailure(root);  
                for (TreeNode treeNode : node.getSons()) {  
                    mid.add(treeNode);  
                }  
            }  
    
            // 广度遍历所有节点设置失败指针 1.存在失败指针 2.不存在到root结束  
            while(mid.size() > 0){  
                // 子节点收集器
                ArrayList<TreeNode> temp = new ArrayList<TreeNode>();  
                for (TreeNode node : mid) {  
                    TreeNode r = node.getParent().getFailure();  
                    // 没有找到,保证最大后缀 (最后一个节点字符相同)  
                    while(r != null && r.getSonNode(node.getCh()) == null){  
                        r = r.getFailure();
                    }  
    
                    // 是根结节点
                    if(r == null){  
                        node.setFailure(root);  
                    }else{  
                        node.setFailure(r.getSonNode(node.getCh()));  
                        // 重叠后缀的包含  
                        for (String result : node.getFailure().getResults()) {  
                            node.addResult(result);  
                        }  
                    }  
                    // 收集子节点  
                    temp.addAll(node.getSons());  
                }  
                mid = temp;  
            }  
        }
    
        /**
         * 根据状态顺序打印树信息
         */
        public static void printTree(){
            // 收集所有节点
            List<TreeNode> nodesList = new ArrayList<TreeNode>();
            // 过程容器 
            List<TreeNode> nodes = Arrays.asList(root);
            while(nodes.size() > 0){
                ArrayList<TreeNode> temp = new ArrayList<TreeNode>();  
                for(TreeNode node : nodes){
                    temp.addAll(node.getSons());
                    nodesList.add(node);
                }
                nodes = temp;
            }
            // 排序
            Collections.sort(nodesList, (a, b) -> a.getStatus().compareTo(b.getStatus()));
            for(TreeNode node : nodesList){
                System.out.println(node.getCh() + " " + node.getDepth() + " " + node.getStatus() + 
                        " " + (node.getFailure() != null ? node.getFailure().getStatus() : "0"));
            }
        }
    
        // 查找全部的模式串  
        public static void acSearch(){
            // 可以找到 转移到下个节点 不能找到在失败指针节点中查找直到为root节点  
            int index = 0;  
            TreeNode mid = root;  
            while(index < Text.length()){  
                TreeNode temp = null;  
    
                while(temp ==null){  
                    temp = mid.getSonNode(Text.charAt(index));  
                    if(mid ==root){  
                        break;  
                    }  
                    if(temp==null){  
                        mid = mid.getFailure();  
                    }  
                }  
                // mid为root 再次进入循环 不需要处理  或者 temp不为空找到节点 节点位移  
                if (temp != null) mid = temp;
    
                for (String result : mid.getResults()) {  
                    System.out.println((index - result.length() + 1) + ":" + index + "=" + result);
                }  
                index++;  
            }  
        } 
    }
    
    class TreeNode{
        // 父节点
        private TreeNode parent;
        // failuere
        private TreeNode failure;
        // 字符
        private char ch;
        // goto表
        private List<TreeNode> sons;
        // 获取子节点
        private Hashtable<Character, TreeNode> sonsHash;  
        // output
        private List<String> results;
        // 深度
        private int depth = 0;
        // 状态
        private Integer status = 0;
    
        public TreeNode(TreeNode parent, char ch) {  
            this.parent = parent;  
            this.ch = ch;  
            results = new ArrayList<String>();  
            sonsHash = new Hashtable<Character, TreeNode>();  
            sons = new ArrayList<TreeNode>();
            if(parent != null)
                depth = parent.getDepth() + 1;
        }  
    
        // 添加一个结果到结果字符中, 状态5量 output : he 和 she
        public void addResult(String result){  
              if(!results.contains(result)) results.add(result); 
        }
    
        // 添加子节点  
        public void addSonNode(TreeNode node){  
            sonsHash.put(node.ch, node);  
            sons.add(node);
        }  
    
        // 设置失败指针并且返回  
        public TreeNode setFailure(TreeNode failure){  
            this.failure = failure;  
            return this.failure;  
        }  
    
        // 获取子节点中指定字符节点  
        public TreeNode getSonNode(char ch){  
            return sonsHash.get(ch);  
        }  
    
        // 获取父节点
        public TreeNode getParent() {
            return parent;
        }
        // 获取字符
        public char getCh() {
            return ch;
        }
        // 获取所有的孩子节点  
        public List<TreeNode> getSons() {
            return sons;
        }
        // 获取搜索的字符串  
        public List<String> getResults() {
            return results;
        }
        // 获取深度
        public int getDepth() {
            return depth;
        }
        public Integer getStatus() {
            return status;
        }
        public void setStatus(Integer status) {
            this.status = status;
        }
        public TreeNode getFailure() {
            return failure;
        }
    }

    心得:

      KMP算法依然是解读AC算法的重要线索,前缀,子串,后缀永远和模式匹配纠缠在一起。
      
      AC状态机实际上更适合用Trie结构来存储。
      
      可以将算法中使用到的goto,fail,output三张表以离线的方式计算出来保存在一个文件中,当AC算法启动时,直接从文件中读取三个表的内容,这样可以有效减少每次AC算法启动时都需要构建三个表所花费的时间。
      
      可以把同深度节点排序,后面查找某状态的指定字符外向边状态,可以使用二分查找,加快速度;

      值得注意的是在AC算法的以上实现中,对于输入字符a的跳转次数是不确定的。因为有可能在输入a后发生失配,需要查找failure表重新跳转。能不能在PMM的基础上实现确定型的有限状态机,即对于任意字符a,都只用进行一次确定的状态跳转?答案是肯定的。在Aho和Corasick论文中给出了处理的方法:构造一个与KMP算法中相似的next表,实现确定性跳转。

    展开全文
  • 多模式匹配算法:AC自动机的C++实现

    千次阅读 2015-03-16 21:00:01
    AC自动机(Aho-Corasick automaton)是用来处理多模式匹配问题的。 基本可认为是TrieTree+KMP。其中KMP是一种单模式匹配算法。 AC自动机的构造要点是失败指针的设置,用于匹配失败时跳转到另一节点继续匹配。同时在...

    AC自动机(Aho-Corasick automaton)是用来处理多模式匹配问题的。

    基本可认为是TrieTree+KMP。其中KMP是一种单模式匹配算法。

    AC自动机的构造要点是失败指针的设置,用于匹配失败时跳转到另一节点继续匹配。同时在匹配的过程中也用来检索其他“同尾”的模式。

    失败指针的设置:

    用BFS。

    对于每个节点,我们可以这样处理:设这个节点上的字母为C,沿着他父亲的失败指针走,直到走到一个节点,他的儿子中也有字母为C的节点。然后把当前节点的失败指针指向那个字目也为C的儿子。如果一直走到了root都没找到,那就把失败指针指向root。

    最开始,我们把root加入队列(root的失败指针显然指向自己),这以后我们每处理一个点,就把它的所有儿子加入队列,直到全部设置完毕。

    要点1:root的孩子的那一层比较特殊,若按照上述算法,它们的失败指针会指向自己,这会在匹配的过程中导致死循环。显然root的子节点的失败指针应指向root,我们应对这一层单独处理。

    要点2:沿着父节点的失败指针走到root之后并不是立即将子节点的失败指针设置为root,而是在root的子节点中找寻字母为C的节点,将它设置为失败指针。若没有才设置为root。这样不会丢失模式只有一个字母的情况。


    匹配过程:

    一开始,Trie中有一个指针t1指向root,待匹配串中有一个指针t2指向串头。

    接下来的操作和KMP很相似:

    若:t2指向的字母,是Trie树中,t1指向的节点的儿子,那么

    ①t2+1,t1改为那个儿子的编号

    如果t1所在的点可以顺着失败指针走到一个绿色点(指TrieTree中单词结尾字母对应的节点),那么以那个绿点结尾的单词就算出现过了。

    否则:t1顺这当前节点的失败指针向上找,直到t2是t1的一个儿子,或者t1指向根。如果t1路过了一个绿色的点,那么以这个点结尾的单词就算出现过了。


    c++实现:

    //TrieTreeNode.h
    #pragma once
    #include<iostream>
    using namespace std;
    
    template<class T>
    class TrieTreeNode
    {
    public:
    	TrieTreeNode(int MaxBranch)//用于构造根节点
    	{
    		MaxBranchNum = MaxBranch;
    		ChildNodes = new TrieTreeNode<T>*[MaxBranchNum];
    		for (int i = 0; i < MaxBranchNum; i++)
    			ChildNodes[i] = NULL;
    		word = NULL;
    		wordlen = 0;
    		FailedPointer = NULL;
    		Freq = 0;
    		ID = -1;
    	}
    public:
    	int MaxBranchNum;//最大分支数;
    	char* word;//单词字符串的指针
    	int wordlen;
    	TrieTreeNode<T> **ChildNodes;
    	int Freq;//词频统计
    	int ID;//构建TrieTree树时的插入顺序,可用来记录字符串第一次出现的位置
    	TrieTreeNode<T> *FailedPointer;
    };


    //TrieTree.h
    #pragma once
    #include<iostream>
    #include"TrieTreeNode.h"
    #include<queue>
    using namespace std;
    
    template<class T>
    class TrieTree
    {
    	//Insert时为节点代表的单词word分配内存,Delete时只修改Freq而不删除word,Search时以Freq的数值作为判断依据,而不是根据word是否为NULL
    public:
    	TrieTree(const int size);
    	~TrieTree(){ Destroy(root); };
    	void Insert(const T* str);//插入单词str
    	void Insert(const T* str, const int num);//插入单词str,带有编号信息
    	int Search(const T* str);//查找单词str,返回出现次数
    	bool Delete(const T* str);//删除单词str
    	void PrintALL();//打印trie树中所有节点对应的单词
    	void PrintPre(const T* str);//打印以str为前缀的单词
    	void SetFailedPointer();//设置匹配失效时的跳转指针
    	int MatchKMP(char* str);//返回str中出现在该TrieTree中的单词个数
    private:
    	void Print(const TrieTreeNode<T>* p);
    	void Destroy(TrieTreeNode<T>* p);//由析构函数调用,释放以p为根节点的树的空间
    private:
    	TrieTreeNode<T>* root;
    	int MaxBranchNum;//最大分支数
    };
    
    
    template<class T>
    void TrieTree<T>::Destroy(TrieTreeNode<T>* p)
    {
    	if (!p)
    		return;
    	for (int i = 0; i < MaxBranchNum; i++)
    		Destroy(p->ChildNodes[i]);
    	if (!p->word)
    	{
    		delete[] p->word;//只是释放了char数组word的空间,指针word本身的空间未释放,由后续的delete p释放
    		p->word = NULL;
    	}
    	delete p;//释放节点空间
    	p = NULL;//节点指针置为空
    	//以上的置NULL的两句无太大意义,但是:编程习惯
    }
    
    template<class T>
    bool TrieTree<T>::Delete(const T* str)
    {
    	TrieTreeNode<T>* p = root;
    	if (!str)
    		return false;
    	for (int i = 0; str[i]; i++)
    	{
    		int index = str[i] - 'a';
    		if (p->ChildNodes[index])
    			p = p->ChildNodes[index];
    		else return false;
    	}
    	p->Freq = 0;
    	p->ID = -1;
    	return true;
    }
    
    template<class T>
    void TrieTree<T>::PrintPre(const T* str)
    {
    	TrieTreeNode<T>* p = root;
    	if (!str)
    		return;
    	for (int i = 0; str[i]; i++)
    	{
    		int index = str[i] - 'a';
    		if (p->ChildNodes[index])
    			p = p->ChildNodes[index];
    		else return;
    	}
    	cout << "以" << str << "为前缀的单词有:" << endl;
    	Print(p);
    }
    
    template<class T>
    int TrieTree<T>::Search(const T* str)
    {
    	TrieTreeNode<T>* p = root;
    	if (!str)
    		return -1;
    	for (int i = 0; str[i]; i++)
    	{
    		int index = str[i] - 'a';
    		if (p->ChildNodes[index])
    			p = p->ChildNodes[index];
    		else return 0;
    	}
    	return p->Freq;
    }
    
    template<class T>
    TrieTree<T>::TrieTree(const int size)
    {
    	MaxBranchNum = size;
    	root = new TrieTreeNode<T>(MaxBranchNum);//根节点不储存字符
    	root->FailedPointer = root;//设置失配指针
    }
    
    template<class T>
    void TrieTree<T>::Insert(const T* str)
    {
    	TrieTreeNode<T>* p = root;
    	int i;
    	for (i = 0; str[i]; i++)
    	{
    		if (str[i]<'a' || str[i]>'z')
    		{
    			cout << "格式错误!" << endl;
    			return;
    		}
    		int index = str[i] - 'a';//下溯的分支编号
    		if (!p->ChildNodes[index])
    			p->ChildNodes[index] = new TrieTreeNode<T>(MaxBranchNum);
    		p = p->ChildNodes[index];
    	}
    	if (!p->word)//该词以前没有出现过
    	{
    		p->word = new char[strlen(str) + 1];
    		strcpy_s(p->word, strlen(str) + 1, str);
    		p->wordlen = i;//设置单词长度
    	}
    	p->Freq++;
    }
    
    template<class T>
    void TrieTree<T>::Insert(const T* str, const int num)
    {
    	TrieTreeNode<T>* p = root;
    	int i;
    	for (i = 0; str[i]; i++)
    	{
    		if (str[i]<'a' || str[i]>'z')
    		{
    			cout << "格式错误!" << endl;
    			return;
    		}
    		int index = str[i] - 'a';//下溯的分支编号
    		if (!p->ChildNodes[index])
    			p->ChildNodes[index] = new TrieTreeNode<T>(MaxBranchNum);
    		p = p->ChildNodes[index];
    	}
    	if (!p->word)//该词以前没有出现过
    	{
    		p->word = new char[strlen(str) + 1];
    		strcpy_s(p->word, strlen(str) + 1, str);
    		p->wordlen = i;
    	}
    	p->Freq++;
    	if (num < p->ID || p->ID == -1)//取最小的num作为当前节点代表的单词的ID
    		p->ID = num;
    }
    
    template<class T>
    void TrieTree<T>::PrintALL()
    {
    	Print(root);
    }
    
    template<class T>
    void TrieTree<T>::Print(const TrieTreeNode<T>* p)
    {
    	if (p == NULL)
    		return;
    	if (p->Freq > 0)
    	{
    		cout << "单词:" << p->word << "	频数:" << p->Freq;
    		if (p->ID >= 0)
    			cout << "		ID:" << p->ID;
    		cout << endl;
    	}
    	for (int i = 0; i < MaxBranchNum; i++)
    	{
    		if (p->ChildNodes[i])
    		{
    			Print(p->ChildNodes[i]);
    		}
    	}
    }
    
    template<class T>
    int TrieTree<T>::MatchKMP(char* str)
    {
    	int count = 0;//str中出现的TrieTree中的单词个数
    	char* p = str;//str中指针
    	TrieTreeNode<T>* node = root;//TrieTree的节点指针
    	while (*p)
    	{
    		if (node->ChildNodes[*p - 'a'])//当前字符匹配成功
    		{
    			TrieTreeNode<T>* temp = node->ChildNodes[*p - 'a']->FailedPointer;
    			while (temp != root)//在匹配的情况下,仍然沿FailedPointer搜索,可检索出所有模式。
    			{
    				if (temp->Freq > 0)
    				{
    					count++;
    					//cout << "temp->wordlen:" << temp->wordlen << endl;
    					cout << (int)(p - str) - temp->wordlen + 1 << "	" << temp->word << endl;//打印已匹配的模式的信息
    				}
    				temp = temp->FailedPointer;
    			}
    			node = node->ChildNodes[*p - 'a'];
    			p++;
    			if (node->Freq > 0)
    			{
    				count++;
    				//cout << "node->wordlen:" << node->wordlen << endl;
    				cout << (int)(p - str) - node->wordlen << "	" << node->word << endl;//打印已匹配的模式的信息
    			}
    		}
    		else//失配,跳转
    		{
    			if (node == root)
    				p++;
    			else
    				node = node->FailedPointer;
    		}
    	}
    	return count;
    }
    
    template<class T>
    void TrieTree<T>::SetFailedPointer()
    {
    	queue<TrieTreeNode<T>*> q;
    	q.push(root);
    	while (!q.empty())
    	{
    		TrieTreeNode<T>* father = q.front();//父节点
    		q.pop();
    		for (int i = 0; i < MaxBranchNum; i++)//对每一个子节点设置FailedPointer
    		{
    			if (father->ChildNodes[i])
    			{
    				TrieTreeNode<T>* child = father->ChildNodes[i];
    				q.push(child);
    				TrieTreeNode<T>* candidate = father->FailedPointer;//从father->FailedPointer开始游走的指针
    				while (true)
    				{
    					if (father == root)
    					{
    						candidate = root;
    						break;
    					}
    					if (candidate->ChildNodes[i])//有与child代表的字母相同的子节点
    					{
    						candidate = candidate->ChildNodes[i];
    						break;
    					}
    					else
    					{
    						if (candidate == root)
    							break;
    						candidate = candidate->FailedPointer;//以上两句顺序不能交换,因为在root仍可以做一次匹配
    					}
    				}
    				child->FailedPointer = candidate;
    			}
    		}
    	}
    }
    



    //main.cpp
    #pragma once
    #include<iostream>
    #include<fstream>
    #include"TrieTree.h"
    using namespace std;
    
    void test(TrieTree<char>* t)
    {
    	char* charbuffer = new char[50];
    	char* cb = charbuffer;
    
    	fstream fin("d:\\words.txt");
    	if (!fin){
    		cout << "File open error!\n";
    		return;
    	}
    	char c;
    	int num = 0;
    	while ((c = fin.get()) != EOF)
    	{
    		if (c >= '0'&&c <= '9')
    			num = num * 10 + c - '0';
    		if (c >= 'a'&&c <= 'z')
    			*cb++ = c;
    		if (c == '\n')
    		{
    			*cb = NULL;
    			t->Insert(charbuffer, num);
    			cb = charbuffer;
    			num = 0;
    		}
    	}
    	fin.close();
    }
    
    
    void main()
    {
    	TrieTree<char>* t = new TrieTree<char>(26);
    	char* c1 = "she";
    	char* c2 = "shee";
    	char* c3 = "he";
    	char* c4 = "e";
    
    	char* s = "shee";//要匹配的串
    	t->Insert(c1);
    	t->Insert(c2);
    	t->Insert(c3);
    	t->Insert(c4);
    
    	//test(t);
    	t->SetFailedPointer();
    	t->PrintALL();
    	cout << endl << "匹配结果为:" << endl;
    	int result = t->MatchKMP(s);
    	cout << "共匹配" << result << "处模式串" << endl;
    	system("pause");
    }

    运行结果:

    对"shee"进行匹配

    模式串为:"shee" "she" "he" "e"





    展开全文
  • 多模式匹配算法-AC算法等

    千次阅读 2017-08-21 11:42:30
    问题一:如果有一个关键词,然后让你在一段长文本中找出这些关键词,如何做?...问题二中,一段长文本中找N个关键词,那么就是多模式匹配,除了朴素算法外,也有一些经典的算法,例如AC算法、BM算法等。
  • AC算法,多模式匹配

    千次阅读 2012-03-05 16:15:48
    AC算法是Alfred V.Aho(《编译原理》(龙书)的作者),和Margaret J.Corasick于1974年提出(与KMP算法同年)的一个经典的多模式匹配算法,可以保证对于给定的长度为n的文本,和模式集合P{p1,p2,...pm},在O(n)时间...
  • Wu-Manber 经典多模式匹配算法

    万次阅读 2013-06-18 22:43:08
    提到多模式匹配算法,就得说一下Wu-Manber算法,其在多模式匹配领域相较于Aho-Corasick算法,就好象在单模式匹配算法中BM算法相较于KMP算法一样,在绝大多数场合,Wu-Manber算法的匹配效率要好于Aho-Corasick算法。...
  • 多模式匹配  多模式匹配就是有个模式串P1,P2,P3…,Pm,求出所有这些模式串在连续文本T1….n中的所有可能出现的位置。  例如:求出模式集合{“nihao”,”hao”,”hs”,”hsr”}在给定文本”...
  • AC 经典多模式匹配算法

    万次阅读 2009-05-23 15:27:00
    今天说说多模式匹配AC算法(Aho and Corasick),感谢追风侠帮忙整理资料,while(1) {Juliet.say("3Q");}。前面学习了BM、Wu-Manber算法,WM由BM派生,不过AC与它们无染,是另外一种匹配思路。 1. 初识AC算法Step1:...
  • 经常会遇到一类需求,在一段字符串中查找所有能匹配上的模式,比如查找一段文字匹配上字典中哪些短语。这时为了高效处理,就会考虑 AC 自动机,即 Aho-Corasick 自动机算法。它的核心思想是通过有限自动机巧妙地将...
  • 一种快速的多模式匹配算法

    千次阅读 2008-10-21 23:04:00
    一种快速的多模式匹配算法一.摘要本文将给出一个简单但非常有效率的多模式匹配算法,这个算法基于压缩编码的思想。该算法在自左向右扫描文本的过程中,根据出现在输入模式中的字符将文本中的字符进行编码。这个简单...
  • 多模式匹配ACBM

    千次阅读 2010-07-10 22:34:00
    回忆下,单模式匹配算法,它可以分成两类: 1. 模式串从左向右匹配(e.g. KMP) 2. 模式串从右向左匹配(e.g. Booyer Moore) BM算法的特点是: 最好情况下算法时间复杂度是(O(m/n)), m是字符串长度,n是pattern长度。...
  • ac自动机(字符串的多模式匹配)

    千次阅读 2018-08-31 06:32:58
    前面已经说过kmp是一种字符串匹配算法...而ac自动机是多模式的字符串匹配算法。也就是给你n个模式串p1,p2,p3.......pn,和一个主串m。,让你找出 这n个模式串在m中的位置。 有的同学可能会进行n次kmp来解决多模式字...
  • 多模式匹配算法

    万次阅读 2010-06-27 22:18:00
    1. 问题原型: 给定一篇网页,其中有很敏感词汇或者无效的词,需要找到一种算法,找到这些敏感词。 2. 如何求解呢? 2.1 第一个简单的思路是: step1: for i = 0 to in #text step2: foreach pattern p step3...
  • 多模式匹配算法:AC算法、WM算法

    千次阅读 2016-03-03 21:33:29
    一、AC(Aho—Corasiek)算法 ...AC(Aho—Corasiek) 多模式匹配算法 AC-BM算法原理与代码实现(模式匹配) 精确单字符串匹配BM算法及其在snort中的C语言实现代码解析 AC算法实例
  • AC算法--多模式匹配(论文解析版)

    万次阅读 2012-09-09 16:02:02
    早在1975年贝尔实验室的两位研究人员Alfred V. Aho 和Margaret J. Corasick就提出了以他们的名字命名的高效的匹配算法---AC算法。...与KMP算法相同,AC算法时至今日仍然在模式匹配领域被广泛应用。  最近本人
  • 朴素模式匹配与KMP模式匹配算法

    千次阅读 2018-07-02 10:15:42
    一、朴素模式匹配朴素模式匹配算法就是遍历主串,然后把待匹配字符串与子串进行比对,先把待匹配子串的第一个字母与主串进行匹配,若匹配成功,则两串的坐标依次 ++,匹配不成功时,主串坐标返回到开始匹配时的坐标...
  • Scala-模式匹配

    千次阅读 2020-08-30 22:58:14
    三、 模式匹配类型 3.1 匹配常量 3.2 匹配类型 3.3 匹配数组 3.4 匹配列表 3.5 匹配元组 3.6 匹配对象及样例类 四、 变量声明中的模式匹配 五、 for表达式中的模式匹配 六、 偏函数中的模式匹配(了解) ...
  • snort 源码分析之模式匹配引擎

    千次阅读 2017-03-20 16:06:05
    模式匹配引擎主要使用多模式匹配算法和单模式匹配算法。先由多模式匹配算法大概确定有哪些规则可能匹配成功,然后再通过单模式匹配算法去精确匹配。其配置格式如下: config detection: search-me...
  • Scala模式匹配

    千次阅读 2019-12-28 22:45:24
    一.Scala的模式匹配 Scala的模式匹配,比java的功能更加全面,应用比较广泛 Scala中提供本类(case class),对模式匹配进行优化 package day1228 object Demo extends App { /** * 模式匹配 * */ //定义一...
  • 模式匹配算法总结

    千次阅读 2019-05-23 19:43:54
    模式匹配是数据结构中字符串的一种基本运算场景,给定一个子串,要求在某个字符串中找出与该子串相同的所有子串。尽管早已可以通过 Python 下的 re 库使用正则表达式高效而简洁地实现模式匹配,但了解相关算法背后...
  • 模式匹配算法

    千次阅读 2015-06-08 07:38:39
    简单模式匹配算法 BF算法(Brute-Force,又称古典的、经典的、朴素的、穷举的) 带回溯,速度慢 算法设计思想: 将主串S的第pos个字符和模式T的第1个字符比较,若相等,继续逐个比较后续字符;若不等,从主串S...
  • KMP模式匹配算法

    千次阅读 2018-11-29 17:14:50
    KMP算法可以说是一个很经典的模式匹配算法了,刚开始并没有看懂,看几遍就好了。 朴素模式匹配算法(KMP算法没提出来之前的常用的匹配算法) 当我们在一篇文章中去搜索一个单词的时候,就是在文章中对这个单词...
  • 朴素模式匹配算法的基本思想: 对主串的每一个字符作为子串开头,与模式串进行匹配。对主串做大循环,每个字符开头做模式串长度的小循环,直到匹配成功或全部遍历完成为止。 代码实现非常简单: int ...
  • KMP算法模式匹配

    千次阅读 2014-07-15 21:49:56
    在一个长串中查找一个子串是较常用的操作。各种信息检索系统,文字处理系统都少不了。本文介绍一个非常著名的KMP模式匹配算法用于子串查找
  • 前言匹配之二维数组法代码匹配之二维数组法原理讲解二维数组构造方法匹配过程及代码实现二维数组法适用于模糊匹配二维表匹配的局限性二...匹配的意思在目标字符串中同时查找模式串,比较常用的
  • scala模式匹配的使用

    千次阅读 2014-11-23 23:25:01
    Scala模式匹配 Tip1:模式总是从上往下匹配,如果匹配不到则匹配case_项(类似Java中的default) Tip2:与Java和C语言不同,不需要在每个分支末尾使用break语句退出(不会掉入下一分支) 1 值匹配 与Java中的值匹配类似 2...
  • 字符串的模式匹配:RK算法

    千次阅读 2017-03-20 15:00:20
    RK算法是由Rabin和Karp共同提出的一个算法。 ... RK算法也可以进行多模式匹配,在论文查重等实际应用中一般都是使用此算法。  时间复杂度:O(MN)(实际应用中往往较快,期望时间为O(M+N))R

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 806,863
精华内容 322,745
关键字:

多模式匹配