首页 > 基础算法 > 字符串处理 > 模式匹配-有限自动机
2014
05-27

模式匹配-有限自动机

模式匹配问题:给一个字符串text: txt[0..n-1] 和 一个模式串 pattern :pat[0..m-1],写一个函数 search(char pat[], char txt[])
打印模式pat在txt中出现的所有位置。通俗点说就是在一个字符串中定位另一个串的算法。

例子:
1)输入:
txt[] = “THIS IS A TEST TEXT”
pat[] = “TES”
输出:
Pattern found at index 10
2) 输入:
txt[] = “AABAACAADAABAAABAA”
pat[] = “AABA”
输出:
Pattern found at index 0
Pattern found at index 9
Pattern found at index 13

模式匹配算法是字符串处理的一个重要算法,在编辑器和数据库中应用广泛。前面一讲讨论过了经典的KMP算法
这里我们学习一种新的算法:基于有限自动机(Finite Automata,FA)的模式搜索算法。思想和KMP算法还是有所类似的,KMP算法我们对模式串pat进行预处理,FA算法中,我们也是对pat进行预处理,构建一个二维数组来代表有限自动机。构建FA是该算法的关键。
只要FA构建好了,搜索是很简单的,我们只需要从FA的第一个状态和text的第一个字符开始,每一步, 我们根据text的下一个字符和当前状态, 通过查找FA,然后进入到新的状态。如果我们能达到最终状态,则说明找到了pattern。因此搜索部分的时间复杂度为O(N).

先来看一下对于模式串 pattern “ACACAGA” 的 FA:

FA2

FA11

FA的构建方法

对于长度为M的pattern字符串,FA的状态个数有M+1个。构造 FA的主要过程为:由当前的状态state和所有可能的字符
得到下一个状态。这里的状态state其实就是指的 0-M 的M+1个数字。
给定一个状态 k 和 一个字符串 x ,怎么得到下一个状态呢? 计算方法为:找出模式串pattern的最长前缀prefix ,同时也是
pat[0...k-1]x后缀。则prefix的长度即为下一个状态。
例如对于 在状态 k=5,字符x=’C'时,对于上面的模式串,pat[0...k-1]x 即为”ACACAC”,对于pattern可以找到符合条件的最长
前缀 prefix为”ACAC”,该prefix同时也是 pat[0...k-1]x 的后缀。长度为4,即下一个状态为4. 上面的表格中 FA[5]['C']=4.

下面的代码中,omputeTF() 函数用来构建FA,但是实际复杂度比较高,为O(m^3*NO_OF_CHARS),其中m是模式串pattern的长度。
NO_OF_CHARS为所有可能得字符的个数。这个实现中 尝试了所有可能的 prefix来找到满足条件的最长prefix,属于比较暴力的算法,其实有更高效的算法,参考 KMP算法中计算next数组(lps数组)的方法。后续给给出该优化算法的实现。

#include<stdio.h>
#include<string.h>
#define NO_OF_CHARS 256

//对于状态k和给定的字符x,返回下一个状态。M为pat的长度
int getNextState(char *pat, int M, int k, int x)
{
    // 因为:pat[0...k-1]x 和 pat 的前面都是是一样的,如果x == pat[k]可直接返回。
    if (k < M && x == pat[k])
        return k+1;

    int ns, i;  // ns 是下一个状态

    // ns 最终是最长的那个  prefix (同时也是pat[0..k-1]x)的后缀
    //从可能得最长的前缀位置开始,找到后break,即为所求
    for (ns = k; ns > 0; ns--)
    {
        if(pat[ns-1] == x)
        {
            for(i = 0; i < ns-1; i++)
            {
                if (pat[i] != pat[k-ns+1+i])
                    break;
            }
            if (i == ns-1)
                return ns;
        }
    }

    return 0;
}

/* 构建FA  */
void computeTF(char *pat, int M, int TF[][NO_OF_CHARS])
{
    int state, x;
    for (state = 0; state <= M; ++state)
        for (x = 0; x < NO_OF_CHARS; ++x)
           TF[state][x] = getNextState(pat, M,  state, x);
}

/* 查找模式串 */
void search(char *pat, char *txt)
{
    int M = strlen(pat);
    int N = strlen(txt);

    //TF数组存储FA有限状态机
    int TF[M+1][NO_OF_CHARS];

    computeTF(pat, M, TF);

    // Process txt over FA.
    int i, state=0;
    for (i = 0; i < N; i++)
    {
       state = TF[state][txt[i]];
       if (state == M)
       {
         printf ("\n patterb found at index %d", i-M+1);
       }
    }
}

// 测试
int main()
{
   char *txt = "AABAACAADAABAAABAA";
   char *pat = "AABA";
   search(pat, txt);
   return 0;
}

参考:http://www.geeksforgeeks.org/searching-for-patterns-set-5-finite-automata/


  1. A猴子认识的所有猴子和B猴子认识的所有猴子都能认识,这句话用《爱屋及乌》描述比较容易理解……

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。