字符串匹配_字符串匹配算法 - CSDN
精华内容
参与话题
  • 字符串匹配——朴素算法、KMP算法

    千次阅读 2015-04-18 15:46:55
    字符串匹配(string match)是在实际工程中经常会碰到的问题,通常其输入是原字符串(String)和子串(又称模式,Pattern)组成,输出为子串在原字符串中的首次出现的位置。通常精确的字符串搜索算法包括朴素搜索算法,...

    字符串匹配(string match)是在实际工程中经常会碰到的问题,通常其输入是原字符串(String)和子串(又称模式,Pattern)组成,输出为子串在原字符串中的首次出现的位置。通常精确的字符串搜索算法包括朴素搜索算法,KMP, BM(Boyer Moore), sunday, robin-karp 以及 bitap。下面分析朴素搜索算法和KMP这两种方法并给出其实现。假设原字符T串长度N,子串P长度为M。

    1.NAIVE—STRING—MATCHING.

    朴素算法,该方法又称暴力搜索,也是最容易想到的方法。

    预处理时间 O(0)

    匹配时间复杂度O(N*M)

    主要过程:从原字符串开始搜索,若出现不能匹配,则从原搜索位置+1继续。

    代码如下:

    void NAIVE_STRING_MATCHING(string T,string P)
    {
    	int n=T.size();
    	int m=P.size();
    	int i;
    	for (int s=0;s<n-m;s++)
    	{
    		for (i=0;i<m;i++)
    		{
    			if (P[i]!=T[s+i])
    			{
    				break;
    			}
    		}
    		if (i==m)
    		{
    			cout<<"pattern occurs with shift  "<<s<<endl;
    		}
    	}
    }

    2.Knuth—Morris—Pratt算法

    简称KMP算法,举例来说,有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”ABCDABD”?

    字符串匹配的KMP算法

    许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命名,起头的那个K就是著名科学家Donald Knuth。

    字符串匹配的KMP算法

    这种算法不太容易理解,网上有很多解释,但读起来都很费劲。直到读到Jake Boxer的文章,我才真正理解这种算法。下面,我用自己的语言,试图写一篇比较好懂的KMP算法解释。

    1.

    字符串匹配的KMP算法

    首先,字符串”BBC ABCDAB ABCDABCDABDE”的第一个字符与搜索词”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以搜索词后移一位。

    2.

    字符串匹配的KMP算法

    因为B与A不匹配,搜索词再往后移。

    3.

    字符串匹配的KMP算法

    就这样,直到字符串有一个字符,与搜索词的第一个字符相同为止。

    4.

    字符串匹配的KMP算法

    接着比较字符串和搜索词的下一个字符,还是相同。

    5.

    字符串匹配的KMP算法

    直到字符串有一个字符,与搜索词对应的字符不相同为止。

    6.

    字符串匹配的KMP算法

    这时,最自然的反应是,将搜索词整个后移一位,再从头逐个比较。这样做虽然可行,但是效率很差,因为你要把”搜索位置”移到已经比较过的位置,重比一遍。

    7.

    字符串匹配的KMP算法

    一个基本事实是,当空格与D不匹配时,你其实知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,继续把它向后移,这样就提高了效率。

    8.

    字符串匹配的KMP算法

    怎么做到这一点呢?可以针对搜索词,算出一张《部分匹配表》(Partial Match Table)。这张表是如何产生的,后面再介绍,这里只要会用就可以了。

    9.

    字符串匹配的KMP算法

    已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。查表可知,最后一个匹配字符B对应的”部分匹配值”为2,因此按照下面的公式算出向后移动的位数:

      移动位数 = 已匹配的字符数 – 对应的部分匹配值

    因为 6 – 2 等于4,所以将搜索词向后移动4位。

    10.

    字符串匹配的KMP算法

    因为空格与C不匹配,搜索词还要继续往后移。这时,已匹配的字符数为2(”AB”),对应的”部分匹配值”为0。所以,移动位数 = 2 – 0,结果为 2,于是将搜索词向后移2位。

    11.

    字符串匹配的KMP算法

    因为空格与A不匹配,继续后移一位。

    12.

    字符串匹配的KMP算法

    逐位比较,直到发现C与D不匹配。于是,移动位数 = 6 – 2,继续将搜索词向后移动4位。

    13.

    字符串匹配的KMP算法

    逐位比较,直到搜索词的最后一位,发现完全匹配,于是搜索完成。如果还要继续搜索(即找出全部匹配),移动位数 = 7 – 0,再将搜索词向后移动7位,这里就不再重复了。

    14.

    字符串匹配的KMP算法

    下面介绍《部分匹配表》是如何产生的。

    首先,要了解两个概念:”前缀”和”后缀”。 “前缀”指除了最后一个字符以外,一个字符串的全部头部组合;”后缀”指除了第一个字符以外,一个字符串的全部尾部组合。

    15.

    字符串匹配的KMP算法

    “部分匹配值”就是”前缀”和”后缀”的最长的共有元素的长度。以”ABCDABD”为例,

      - ”A”的前缀和后缀都为空集,共有元素的长度为0;

    - ”AB”的前缀为[A],后缀为[B],共有元素的长度为0;

    - ”ABC”的前缀为[A, AB],后缀为[BC, C],共有元素的长度0;

    - ”ABCD”的前缀为[A, AB, ABC],后缀为[BCD, CD, D],共有元素的长度为0;

    - ”ABCDA”的前缀为[A, AB, ABC, ABCD],后缀为[BCDA, CDA, DA, A],共有元素为”A”,长度为1;

    - ”ABCDAB”的前缀为[A, AB, ABC, ABCD, ABCDA],后缀为[BCDAB, CDAB, DAB, AB, B],共有元素为”AB”,长度为2;

    - ”ABCDABD”的前缀为[A, AB, ABC, ABCD, ABCDA, ABCDAB],后缀为[BCDABD, CDABD, DABD, ABD, BD, D],共有元素的长度为0。

    16.

    字符串匹配的KMP算法

    “部分匹配”的实质是,有时候,字符串头部和尾部会有重复。比如,”ABCDAB”之中有两个”AB”,那么它的”部分匹配值”就是2(”AB”的长度)。搜索词移动的时候,第一个”AB”向后移动4位(字符串长度-部分匹配值),就可以来到第二个”AB”的位置。

    KMP算法主要分为两个部分:

    一、求子串P部分匹配值数组;

    上面已经分析过,具体代码如下,其中pi指的是部分匹配数组;

    void COMPUTE_PREIFX_FUNCTION(string P,vector<int>& pi)
    {
    	int m=P.size();
    	pi[0]=0;
    	pi[1]=0;
    	int k=0;
    	for (int q=2;q<m;q++)
    	{
    		while (k>0&&P[k+1]!=P[q])
    		{
    			k=pi[k];
    		}
    		if (P[k+1]==P[q])
    		{
    			k=k+1;
    		}
    		pi[q]=k;
    	}
    }

    二、求字符匹配位置;

    按上面分析给出如下代码,为了方便,我们给T,P前面分别增加一个字符“%”和“*”,这样字符串中的第i个字符在代码中的下标也为i,这样可以防止数组溢出,易于理解。

    void KMP_MATCHER(string &T,string &P)
    {
    	T="%"+T;
    	P="*"+P;
    	int m=P.size();
    	vector<int> pi(m);
    	int n=T.size();
    	COMPUTE_PREIFX_FUNCTION(P,pi);
    	int q=0;
    	int i;
    	for (i=1;i<n;i++)
    	{
    		while (q>0&&P[q+1]!=T[i])
    		{
    			q=pi[q];
    		}
    		if (P[q+1]==T[i])
    		{
    			q=q+1;
    		}
    		if (q==m-1)
    		{
    			cout<<"pattern occurs with shift  "<<i-q<<endl;
    			q=pi[q];
    		}
    	}
    }
    完整代码如下:

    头文件:

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    void COMPUTE_PREIFX_FUNCTION(string P,vector<int>& pi);
    void KMP_MATCHER(string &T,string &P);
    void NAIVE_STRING_MATCHING(string T,string P);
    main函数:

    #include"head.h"
    
    void main()
    {
    	string T="BBC ABCDAB ABCDABCDABDEFABCDABDff";
    	string P="ABCDABD";
    	cout<<"NAIVE:"<<endl;
    	NAIVE_STRING_MATCHING(T,P);
    	cout<<"KMP:"<<endl;
    	KMP_MATCHER(T,P);
    }
    void COMPUTE_PREIFX_FUNCTION(string P,vector<int>& pi)
    {
    	int m=P.size();
    	pi[0]=0;
    	pi[1]=0;
    	int k=0;
    	for (int q=2;q<m;q++)
    	{
    		while (k>0&&P[k+1]!=P[q])
    		{
    			k=pi[k];
    		}
    		if (P[k+1]==P[q])
    		{
    			k=k+1;
    		}
    		pi[q]=k;
    	}
    }
    void KMP_MATCHER(string &T,string &P)
    {
    	T="%"+T;
    	P="*"+P;
    	int m=P.size();
    	vector<int> pi(m);
    	int n=T.size();
    	COMPUTE_PREIFX_FUNCTION(P,pi);
    	int q=0;
    	int i;
    	for (i=1;i<n;i++)
    	{
    		while (q>0&&P[q+1]!=T[i])
    		{
    			q=pi[q];
    		}
    		if (P[q+1]==T[i])
    		{
    			q=q+1;
    		}
    		if (q==m-1)
    		{
    			cout<<"pattern occurs with shift  "<<i-q<<endl;
    			q=pi[q];
    		}
    	}
    }
    
    void NAIVE_STRING_MATCHING(string T,string P)
    {
    	int n=T.size();
    	int m=P.size();
    	int i;
    	for (int s=0;s<n-m;s++)
    	{
    		for (i=0;i<m;i++)
    		{
    			if (P[i]!=T[s+i])
    			{
    				break;
    			}
    		}
    		if (i==m)
    		{
    			cout<<"pattern occurs with shift  "<<s<<endl;
    		}
    	}
    }

    运行结果如下:



    ABCDABD继BBC ABCDAB ABCDABCDABDEFABCDABDff第15个元素出现了一次,继第24个元素之后出现了一次。

    本文代码参照算法导论第32章伪代码编写;

    部分内容参考:http://blog.jobbole.com/39066/





    展开全文
  • 字符串匹配问题

    2017-11-01 21:19:24
    * 字符串匹配问题 * 给定字符串str, 不含有'.' 和 '*',字符串exp,可以 * 含有'.'和 '*',且'*'不是exp的首字符,任意两个'*' * 不相邻。 * exp中的'.'代表任意一个字符, '*' 代表'*'之前的字符 * 可以有0个...
    /**
     * Created by lxw, liwei4939@126.com on 2017/11/1.
     * 字符串匹配问题
     * 给定字符串str, 不含有'.' 和 '*',字符串exp,可以
     * 含有'.'和 '*',且'*'不是exp的首字符,任意两个'*'
     * 不相邻。
     * exp中的'.'代表任意一个字符, '*' 代表'*'之前的字符
     * 可以有0个或多个
     * 判断str是否能被exp匹配
     */
    public class stringMatch {
    
        //判断两个数组是否有效
        public boolean isValid(char[] s, char[] e){
            for (int i=0; i< s.length; i++){
                if(s[i] == '.' || s[i] == '*'){
                    return false;
                }
            }
            for (int i=0; i< e.length; i++){
                if(e[i] == '*' && (i==0 || e[i-1] =='*')){
                    return false;
                }
            }
            return true;
        }
    
        public boolean isMatch(String str, String exp){
            if(str == null || exp == null){
                return false;
            }
            char[] arrStr = str.toCharArray();
            char[] arrExp = exp.toCharArray();
            return isValid(arrStr, arrExp) ? process(arrStr, arrExp, 0, 0) : false;
        }
    
        public boolean process(char[] s, char[] e, int si, int ei){
            if(ei == e.length){
                return si == s.length;
            }
            if(ei + 1 ==e.length || e[ei] != '*'){
                return si != s.length && (e[ei] == s[si] || e[ei] == '.')
                        && process(s, e, si+1, ei+1);
            }
            while (si != s.length && (e[ei] == s[si]) || e[ei] == '.'){
                if(process(s, e, si, ei+2)){
                    return true;
                }
                si++;
            }
            return process(s, e, si, ei+2);
        }
    
        //动态规划求解
        public boolean isMatchDP(String str, String exp){
            if(str == null || exp == null){
                return false;
            }
            char[] s = str.toCharArray();
            char[] e = exp.toCharArray();
            if(!isValid(s, e)){
                return false;
            }
            boolean[][] dp = initDP(s, e);
            for (int i = s.length -1; i > -1; i--){
                for (int j = e.length -2; j>-1; j--){
                    if(e[j+1] != '*'){
                        dp[i][j] = (s[i] == e[j] || e[j] == '.') && dp[i+1][j+1];
                    } else {
                        int si = i;
                        while (si != s.length && (s[si] == e[j] || e[j] == '.')){
                            if(dp[si][j+2]){
                                dp[i][j] = true;
                                break;
                            }
                            si++;
                        }
                        if(dp[i][j] != true){
                            dp[i][j] = dp[si][j+2];
                        }
                    }
                }
            }
            return dp[0][0];
        }
    
        public boolean[][] initDP(char[] s, char[] e){
            int slen = s.length;
            int elen = e.length;
            boolean[][] dp = new boolean[slen+1][elen +1];
            dp[slen][elen] = true;
            for (int j= elen -2; j > -1; j = j-2){
                if(e[j] != '*' && e[j+1] == '*'){
                    dp[slen][j] = true;
                } else {
                    break;
                }
            }
            if(slen >0 && elen >0){
                if(e[elen -1] == '.' || e[elen - 1] == s[slen -1]){
                    dp[slen-1][elen-1] = true;
                }
            }
            return dp;
        }
    
        public static void main(String[] args){
            stringMatch tmp = new stringMatch();
    
            String str1 = "abc";
            String exp1 = "a.c";
            System.out.println(tmp.isMatch(str1, exp1));
    
            String str2 = "abcd";
            String exp2 = ".*";
            System.out.println(tmp.isMatchDP(str2, exp2));
        }
    }
    

    展开全文
  • 字符串算法之KMP(字符串匹配

    千次阅读 2018-06-17 16:51:47
      给定一个主(以 S 代替)和模式(以 P 代替),要求找出 P 在 S 中出现的位置,此即的模式匹配问题。   Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳...

    一、背景

      给定一个主串(以 S 代替)和模式串(以 P 代替),要求找出 P 在 S 中出现的位置,此即串的模式匹配问题。

      Knuth-Morris-Pratt 算法(简称 KMP)是解决这一问题的常用算法之一,这个算法是由高德纳(Donald Ervin Knuth)和沃恩·普拉特在1974年构思,同年詹姆斯·H·莫里斯也独立地设计出该算法,最终三人于1977年联合发表。

      在继续下面的内容之前,有必要在这里介绍下两个概念:真前缀真后缀

    这里写图片描述

      由上图所得, “真前缀”指除了自身以外,一个字符串的全部头部组合;”真后缀”指除了自身以外,一个字符串的全部尾部组合。

    二、KMP字符串匹配算法

    1、算法流程

    (1)

      首先,主串”BBC ABCDAB ABCDABCDABDE”的第一个字符与模式串”ABCDABD”的第一个字符,进行比较。因为B与A不匹配,所以模式串后移一位。

    这里写图片描述

    (2)

      直到主串有一个字符,与模式串的第一个字符相同为止。

    这里写图片描述

    (3)

      接着比较主串和模式串的下一个字符,直到主串有一个字符,与模式串对应的字符不相同为止。

    这里写图片描述

      一个基本事实是,当空格与D不匹配时,你其实是已经知道前面六个字符是”ABCDAB”。KMP算法的想法是,设法利用这个已知信息,不要把”搜索位置”移回已经比较过的位置,而是继续把它向后移,这样就提高了效率。

    (4)

      怎么做到这一点呢?可以针对模式串,设置一个跳转数组int next[],这个数组是怎么计算出来的,后面再介绍,这里只要会用就可以了。

    这里写图片描述

    (5)

      已知空格与D不匹配时,前面六个字符”ABCDAB”是匹配的。根据跳转数组可知,不匹配处D的next值为2,因此接下来从模式串下标为2的位置开始匹配。

    这里写图片描述

      因为空格与C不匹配,C处的next值为0,因此接下来模式串从下标为0处开始匹配。

    (6)

    这里写图片描述

      因为空格与A不匹配,此处next值为-1,表示模式串的第一个字符就不匹配,那么直接往后移一位。

    (7)

    这里写图片描述

      逐位比较,直到发现C与D不匹配。于是,下一步从下标为2的地方开始匹配。

    (8)

      逐位比较,直到模式串的最后一位,发现完全匹配,于是搜索完成。

    这里写图片描述

    2、next数组是如何求出的

      next数组的求解基于“真前缀”和“真后缀”,即next[i]等于P[0]…P[i - 1]最长的相同真前后缀的长度(请暂时忽视i等于0时的情况,下面会有解释)。

    这里写图片描述

    这里写图片描述
    这里写图片描述

      那么,为什么根据最长相同真前后缀的长度就可以实现在不匹配情况下的跳转呢?举个代表性的例子:假如i = 6时不匹配,此时我们是知道其位置前的字符串为ABCDAB,仔细观察这个字符串,首尾都有一个AB,既然在i = 6处的D不匹配,我们为何不直接把i = 2处的C拿过来继续比较呢,因为都有一个AB啊,而这个AB就是ABCDAB的最长相同真前后缀,其长度2正好是跳转的下标位置。

    3、next数组的实现

    void cal_next(string &str, vector<int> &next)
    {
        const int len = str.size();
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < len - 1)
        {
            if (k == -1 || str[j] == str[k])
            {
                ++k;
                ++j;
                next[j] = k;//表示第j个字符有k个匹配(“最大长度值” 整体向右移动一位,然后初始值赋为-1)
            }
            else
                k = next[k];//往前回溯
        }
    }

    (1)i和j的作用

      i和j就像是两个”指针“,一前一后,通过移动它们来找到最长的相同真前后缀。

    (2)if…else…语句里做了什么?

    这里写图片描述

      假设i和j的位置如上图,由next[i] = j得,也就是对于位置i来说,区段[0, i - 1]的最长相同真前后缀分别是[0, j - 1]和[i - j, i - 1],即这两区段内容相同

      按照算法流程,if (P[i] == P[j]),则i++; j++; next[i] = j;;若不等,则j = next[j],见下图:

    这里写图片描述

      next[j]代表[0, j - 1]区段中最长相同真前后缀的长度如图,用左侧两个椭圆来表示这个最长相同真前后缀,即这两个椭圆代表的区段内容相同;同理,右侧也有相同的两个椭圆。所以else语句就是利用第一个椭圆和第四个椭圆内容相同来加快得到[0, i - 1]区段的相同真前后缀的长度。

      j == -1意义就是为了特殊边界判断。

    三、KMP算法demo

    #include <iostream>
    #include <string>
    #include <vector>
    using namespace std;
    
    //部分匹配表
    void cal_next(string &str, vector<int> &next)
    {
        const int len = str.size();
        next[0] = -1;
        int k = -1;
        int j = 0;
        while (j < len - 1)
        {
            if (k == -1 || str[j] == str[k])
            {
                ++k;
                ++j;
                next[j] = k;//表示第j个字符有k个匹配(“最大长度值” 整体向右移动一位,然后初始值赋为-1)
            }
            else
                k = next[k];//往前回溯
        }
    }
    
    vector<int> KMP(string &str1, string &str2, vector<int> &next)
    {
        vector<int> vec;
        cal_next(str2, next);
        int i = 0;//i是str1的下标
        int j = 0;//j是str2的下标
        int str1_size = str1.size();
        int str2_size = str2.size();
        while (i < str1_size && j < str2_size)
        {
            //如果j = -1,或者当前字符匹配成功(即S[i] == P[j]),
            //都令i++,j++. 注意:这里判断顺序不能调换!
            if (j == -1 || str1[i] == str2[j])
            {
                ++i;
                ++j;
            }
            else
                j = next[j];//当前字符匹配失败,直接从str[j]开始比较,i的位置不变
            if (j == str2_size)//匹配成功
            {
                vec.push_back(i - j);//记录下完全匹配最开始的位置
                j = -1;//重置
            }
        }
        return vec;
    }
    
    int main(int argc, char const *argv[])
    {
        vector<int> vec(20, 0);
        vector<int> vec_test;
        string str1 = "bacbababadababacambabacaddababacasdsd";
        string str2 = "ababaca";
        vec_test = KMP(str1, str2, vec);
        for (const auto v : vec_test)
            cout << v << endl;
        return 0;
    }

      KMP时间复杂度:O(m+n)。

    四、KMP算法的应用

    1、求其中出现重复的任意一个字符

      先求next数组,next[j]=k,k > 0 时,就返回j,p[j]就是出现重复的字符。

    这里写图片描述

    2、求最长的重复子串

      求最长的重复子串,就是求next[j]=k,求出k的最大值。

    这里写图片描述

    转自:https://segmentfault.com/a/1190000008575379
    https://blog.csdn.net/willinux20130812/article/details/47133425

    展开全文
  • 字符串匹配算法

    千次阅读 2010-05-25 19:48:00
    转自:http://kofsky.javaeye.com/blog/283247 字符串匹配定义:文本是一个长度为n的数组T[1…n], 模式是以个长度mP和T的元素都是有限字母表∑中的字符1.字符串朴素匹配也就是蛮力匹配,每次移动一个步长,然后匹配...

    转自:http://kofsky.javaeye.com/blog/283247

     

    字符串匹配定义:文本是一个长度为n的数组T[1…n], 模式是以个长度m<=n的数组P[1…m]
    P和T的元素都是有限字母表∑中的字符

    1.字符串朴素匹配
    也就是蛮力匹配,每次移动一个步长,然后匹配,时间复杂度O((n-m+1)m)

    2.Rabin-Karp算法
    Rabin-Karp算法的思想是将模式串P表达为一个值,这样每次进行串匹配的时候,只需要比较这个值就可以了,而不需要对m个字符串进行m次比较。
    核心思想是用 一个值 来代替 整个字符串 来参与比较
    比如以十进制为例,文本串为'1234567',模式串为'234'(其值为234),当搜索指针指向第一个字符'1'时,计算出串'123'的值为123,直接与模式串的值234进行比较,不匹配,那么就表明此时模式串匹配失败,将搜索指针移向下一个字符。
    如何用 值 来代表 字符串?
    想象一下将字符串转换为数值的情形
    计算串"123"的值:1*100+2*10+3*1 = 123
        串"6789"的值:6*1000+7*100+8*10+9*1 = 6789
                     
    十进制字母表只有0-9,因此选取基数10可以完成的表述整个串
    对于Ascii字母表,则可以选取基256。
    因此,将一个串表述成一个值是可行的,其时间复杂度为O(m),其中m为串的长度。
    对于文本串T[1…n],可以在O(m)的时间复杂度计算出前m个字符T[1…m]的值。
    而T[2…m+1],T[3…m+2],...T[n-m+1…n]的值,可以在O(n-m)的时间计算出来(动态规划)。
    新的问题:值太大,溢出?
    通过一个值来表述一个串以后,如果串比较长,那么这个表述串的这个值自然会比较大,而且,可能会溢出。很自然的解决办法是对这个值取模,将它限制到一个固定的范围内。
    那么问题又来了,模运算是多对一映射,比如,55和66对11取模后都是0,但是它们的值并不相等。
    因此,取模运算会导致一个新的问题,就是伪命中。也就是,模运算匹配,但串本身并不匹配。
    可以显式的检查T[i…m+i]与P[1…m]是否相等。
    假设计算的值对q取模,倘若q够大,那么T[i…m+i]的值与P[1…m]的值发生伪命中的几率就会比较低,那么额外的测试时间就足够低了。

    这样看来,对字符串求值,通过值来进行串的匹配,更像一个启发式的思想,对文本串进行一次过滤,然后在进行逐字匹配。

    由于每次在判定模式串是否匹配时,只需要进行一次比较,因此匹配过程中的期望时间复杂度为O(n-m+1),这个时间没有加上对模式串求值的时间O(m)。最坏是时间复杂度也为O((n-m+1)m),也就是每一次唯一产生的值都与串的值取模相等,但实际情况下比蛮力匹配要快许多。

    3.FA
    针对模式串,构造一个有穷自动机,那么,有穷自动机接收的语言就是该模式串匹配的句子。
    对于每个模式串,都存在一个字符串匹配自动机,必须在预处理阶段,根据模式构造出相应的自动机后,才能利用它来搜索字符串。构造自动机的核心是构造其状态转移函数。
    这种方法功能比较强大,因为它可以搜索以正则式表达的模式串。而其他算法则不能。

    4.KMP
    先看一个例子。文本串T为bababaabcccb,模式P为ababaca

    如图所示。此时,红色的5个字符ababa已经匹配,

    从字符c开始不匹配。这时候开始移动模式P。到底该移动几个字符呢?朴素的字符串匹配移动一位,然后重新开始比较。但是根本模式本身的信息,移动s'=s+1是无效的,s'=s+2才有可能导致一个成功的匹配。因为模式P的前5个字符里,ababa的前面三个字符aba同时也是ababa的后缀。也就是说,P的最长前缀同时也是P5的的一个真后缀。这些信息是可以被预先计算的,用前缀函数π来表示。在位移s处有q个字符成功匹配,那下一个可能有效的位移为s'=s+(q-π[q]).

    首先假定文本串从第s个位置开始与模式匹配,共匹配q个字符,匹配第q+1个字符时失败,即满足:P[1…q]=T[s+1…s+q],那么,我们的目标就是,寻找一个位移s',使得移动1,2,..s'-1都是不可能导致与模式P匹配成功,只有移动s',才有可能使得与模式P匹配成功。那该怎么寻找这个位移呢?关键就在这个模式本身了。

    如果P[1…q]已经匹配成功,在q+1处匹配失败,倘若已知P[1…k]=P[q-k+1…q](k<q)且k是满足如上等式条件的最大的k,那么,直接移动q-k个位置就可以使得前面的k个字符相匹配。

    这个k就包含了模式串本身的信息。它预先被计算,被定义为前缀函数。定义如下:
     
    模式P的前缀函数是函数π(0,1,2,...,m-1}→{0,1,2,..,m-1}并满足
    π[q]=max{k:k<q且Pk是Pq的后缀,即P[1…k]=P[q-k+1…q]},
    π[q]是Pq的真后缀P的最长前缀的长度。

    下面是前缀函数的一个计算例子。

    计算前缀函数本身就是一个模式串“自我匹配”的过程。KMP的核心也在于通过前缀函数来减少不必要的比较而加快字符串的匹配速度。前缀函数里面包含了模式串的部分匹配信息,也就是当把模式串的前面部分字符移动一段位移后在模式中重复出现,那么这个部分匹配信息就可以用在串匹配中。

    也可以看这个,写的还比较详细:
    http://jpkc.nwu.edu.cn/datastr/study_online/newsite/pluspage/kmp.htm


    5.BM
    BM算法有几个要点
    1.从右向左进行比较,也就是比较次序为P[m],P[m-1]...
    2.当某趟比较中出现不匹配的字符时,BM采用两条启发式规则计算模式串移动的距离,即bad character

    shift rule坏字符和good suffix shift rule好后缀规则。
    坏字符与好后缀的定义
    Index:    0 1 2 3 4 5 6 7 8 9 10 11
    Text:     k s e a b c d e f a b c a
    Pattern: d e c a b c
               
    从右往左进行匹配,第一个mismatch的字符c就是坏字符,后面已经成功匹配的字串abc就是好后缀。
    如果字符没有在模式串中


    1) 坏字符规则
       P中的某个字符与T中的某个字符不相同时使用坏字符规则右移模式串P,P右移的距离可以通过delta1函数

    计算出来。delta1函数的定义如下:
        delta1(x) = 如果字符x在P中未出现,则为 m(模式长度); 否则 m-k, j是最大的整数使得P[k]=字符x,

    用数学表达式则为:m - max{k|P[k] = x, 1 <= k <= m};

    解释一下,如果字符x在模式P中没有出现,那么从字符x开始的m个文本显然不可能与P匹配成功,直接全部跳

    过该区域即可。如果x在模式P中出现,则以该字符进行对齐。


    2) 好后缀规则
       P中的某一子串P[j-s+1..m-s]与已比较部分P[j+1..m]相同,可让P右移s位。
       delta2的定义如下:
       delta2(j)= {s|P[j+1..m]=P[j-s+1..m-s])&&(P[j]≠P[j-s])(j>s)}
       (这部分还看得晕乎晕乎的,下次在来完善)

    贴个BM例子

     

    移动的时候,取两者较大值作为位移值移动。

    BM算法在字母表很大,模式串很长时尤其适用,能够显著提高匹配速度。
    实际应用中,BM算法比同样具有O(m+n)时间复杂度的KMP算法效率高出3-5倍。具体来说,BM算法的预处理阶段的时间空间复杂性是O(m+n),查找阶段的时间复杂性是O(mn),最好情况下的性能是O(n/m)。


    参考:
    前面几个算法主要参考《算法导论》
    BM算法参考
    http://www.cs.utexas.edu/users/moore/best-ideas/string-searching/index.html
    http://www-igm.univ-mlv.fr/~lecroq/string/node14.html

     

     

     

     

     

     

     

    当问题的有效子串只有一个的时候,用KMP:给出1个单词,再给出一段包含m个字符的文章,让你找出这个单词是否在文章里出现过。

    有效子串有一大堆的时候,可以用AC自动机(Aho-Corasick automation):给出n个单词,再给出一段包含m个字符的文章,让你找出有多少个单词在文章里出现过。

    比较新的,还有一个Sunday算法。比较简单,而且快。

    同时,这里有一篇相关介绍论文《一种可做特殊用途的字符串匹配算法》(纪福全 朱战立),可供参考:

    字符串匹配就是在一个字符串中查找模式串的一个或所有出现。字符串匹配用途很广泛。例如,在拼写检查、语言翻译、数据压缩、搜索引擎、网络入侵检测、计算机病毒特征码匹配以及DNA序列匹配等应用中,都需要进行字符串匹配。已经提出了许多字符串匹配算法。传统的有BF算法[2,3]、KMP算法[2,3]等,最近提出的有BM算法[2,4]、Sunday算法[2,3]等。

    相关算法分析    字符串模式匹配的含义是:在主串S中,从位置start开始查找是否存在模式串(也称作模式串)T,如在主串S中查找到一个与模式串T相同的模式串,则模式串与主串匹配;如在主串S中未查找到一个与模式串T相同的模式串,则不匹配 [1] 。首先作如下假设:

    主串S:S[1…N],长度为N;模式串T:T[1…M],长度为M;N≥M;

    BF算法     BF(Brute Force)算法核心思想是:首先S[1]和T[1]比较,若相等,则再比较S[2]和T[2],一直到T[M]为止;若S[1]和P[1]不等,则T向右移动一个字符的位置,再依次进行比较。如果存在k,1≤k≤N,且S[k+1…k+M]=T[1…M],则匹配成功;否则失败。该算法最坏情况下要进行M*(N-M+1)次比较,时间复杂度为O(M*N)。

    KMP算法    KMP(Knuth-Morris-Pratt)算法核心思想是:在发生失配时,主串不需要回溯,而是利用已经得到的“部分匹配”结果将模式串右移尽可能远的距离,继续进行比较。这里要强调的是,模式串不一定向右移动一个字符的位置,右移也不一定必须从模式串起点处重新试匹配,即模式串一次可以右移多个字符的位置,右移后可以从模式串起点后的某处开始试匹配。
    假设发生失配时,S[i]≠T[j],1≤i≤N,1≤j≤M。则下一轮比较时,S[i]应与T[next[j]]对齐往后比较:

    如T=“abaabcac”,则

    BM算法    对于给出的长度为m的模式串T=T&&05;···Tm和主串S=S&&05;···Sn,实现BM算法需要一个辅助数组bm[ ]。它用字符值作为数组的下标,数组的大小依赖于可能出现的字符多少,与模式串的大小无关。对于需要进行中文关键字的匹配,需要扩充ASCII字符集,数组大小则为256。对于任意x属于集合Σ→{1,2,···,256},bm[x]的值为:

    该数组每个字符对应的项记录着该字符在模式串中最后一次出现的位置。BM算法思想是:假如在执行主串位置i起“返前”的一段与模式串T从右向左的字符匹配中,如果模式串T全部字符匹配,则匹配成功;否则需要右移,开始新的一轮匹配,假设匹配不成功发生在模式串中的位置j,由主串匹配不成功字符Si-m+j查找辅助数组得到该字符在模式串T中的最后出现的位置值bm[Si-m+j]。如果bm[Si-m+j]等于零,表示字符Si-m+j不在模式串T中,则模式串跳过该字符,在该字符下一个位置对齐;如果bm[Si-m+j]大于j,表示这个字符在模式串中最后出现的位置在j的左边,则模式串T右移对齐字符Si-m+j;如果bm[Si-m+j]小于j,表示这个字符在模式串中最后出现的位置在j的右边,模式串不能左移,就右移一格。移动量为shift=max(1,m-bm[i-m+j])。

    Sunday算法    Sunday算法是Daniel M.Sunday于1990年提出的一种比BM算法搜索速度更快的算法。其核心思想是:在匹配过程中,模式串并不被要求一定要按从左向右进行比较还是从右向左进行比较,它在发现不匹配时,算法能跳过尽可能多的字符以进行下一步的匹配,从而提高了匹配效率。
    假设在发生不匹配时S[i]≠T[j],1≤i≤N,1≤j≤M。此时已经匹配的部分为u,并假设字符串u的长度为L。如图1。明显的,S[L+i+1]肯定要参加下一轮的匹配,并且T[M]至少要移动到这个位置(即模式串T至少向右移动一个字符的位置)。

    图1 Sunday算法不匹配的情况    分如下两种情况:
    (1) S[L+i+1]在模式串T中没有出现。这个时候模式串T[0]移动到S[T+i+1]之后的字符的位置。如图2。

    图2 Sunday算法移动的第1种情况
    (2)S[L+i+1]在模式串中出现。这里S[L+i+1]从模式串T的右侧,即按T[M-1]、T[M-2]、…T[0]的次序查找。如果发现S[L+i+1]和T中的某个字符相同,则记下这个位置,记为k,1≤k≤M,且T[k]=S[L+i+1]。此时,应该把模式串T向右移动M-k个字符的位置,即移动到T[k]和S[L+i+1]对齐的位置。如图3。

    图3 Sunday算法移动的第2种情况
    依次类推,如果完全匹配了,则匹配成功;否则,再进行下一轮的移动,直到主串S的最右端结束。该算法最坏情况下的时间复杂度为O(N*M)。对于短模式串的匹配问题,该算法执行速度较快。

    实验结果     为了评测该算法的性能,随机的抽取一段文本和模式串,并在同一台计算机上用不同的算法进行匹配。测试文本主串S="From automated teller machines and atomic clocks to mammograms and semiconductors,innumerable products and services rely in some way on technology,measurement,and standards provided by the National Institute of Standards and Technology",模式串T="products and services"。分别用BF算法、KMP算法、BM算法、Sunday算法和ZZL算法在同一台计算机上进行匹配计算,并统计每种算法匹配时总的字符匹配次数。测试结果如表1。
    表1 匹配算法实验结果算法:
                                                    BF KMP BM Sunday ZZL
    一次匹配的总的字符匹配次数 116 95    108 110         23

    ZZL是该文作者提出的一个算法:先预处理查找模式串首字符在主串中的所有出现位置,并将其保存在一个数组中。字符串匹配算法就可以从查找到的模式串在主串中的位置开始,匹配模式串首字母之后的其余部分。此时,采用BF算法即可,并可设置一个计数器,记录匹配次数。对于频繁使用的要匹配的主串和模式串来说,由于预先保存了模式串在主串中的所有存储位置,所以ZZL算法的匹配速度会非常快。(前提是已经进行过预处理)

    展开全文
  • 字符串匹配原理及实现(C++版)

    千次阅读 2018-12-07 09:35:42
    字符串匹配原理及实现(C++版)1. 字符串匹配概念2. BF3. KMP4. BM5. 性能总结 1. 字符串匹配概念 2. BF 3. KMP 4. BM 5. 性能总结
  • 字符串匹配(C语言)

    千次阅读 2018-11-26 13:36:41
    给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。 有效字符串需满足: 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符...
  • 字符串匹配(java版)

    千次阅读 2018-05-05 21:25:11
    发现博客上对于字符串匹配的java资料很少,自己整理一下。参考资料:点击打开链接,点击打开链接字符串匹配(string match)是在实际工程中经常会碰到的问题,通常其输入是原字符串(String)和子串(又称模式,Pattern...
  • 字符串匹配——Sunday算法

    万次阅读 多人点赞 2016-07-08 13:05:40
    字符串匹配——Sunday算法基本思想及举例Sunday算法由Daniel M.Sunday在1990年提出,它的思想跟BM算法很相似:1只不过Sunday算法是从前往后匹配,在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。...
  • 正则表达式(一)字符串匹配

    万次阅读 2018-10-25 09:25:13
    正则表达式介绍简单的模式字符匹配方括号 [ ]反斜杠 \特殊字符重复的事情元字符 *元字符 +元字符 ?元字符 {m,n} 正则表达式(Regular expressions 也称为 REs,或 regexes 或 regex patterns),本质上是一个微小的...
  • 字符串匹配算法综述

    万次阅读 多人点赞 2018-07-22 21:45:46
    字符串匹配算法综述 字符串匹配算法综述:BF、RK、KMP、BM、Sunday 字符串匹配算法,是在实际工程中经常遇到的问题,也是各大公司笔试面试的常考题目。此算法通常输入为原字符串(string)和子串(pattern),要求...
  • 字符串匹配

    千次阅读 2019-07-04 17:25:21
    字符串A中查找字符串B,那字符串A就是主串,字符串B就是模式串。 我们把主串的长度记作n,模式串的长度记作m。因为我们是在主串中查找模式串,所以n>m。 几种单模式串匹配算法 BF(暴力)算法 RK算法 BM算法 ...
  • 一般的字符串模式匹配算法是类似下面的逐次匹配,举例说明如下 主串s=ababcabcacbab 从串t=abcac 一般匹配方法如下图所示 代码如下 int index(string s,string t) {  int i=0,j=0;  int l1=s.length();  ...
  • oracle文字与格式字符串匹配的解决  oracle的日期时间类型 在往oracle的date类型插入数据的时候,记得要用to_date()方法。 如insert into CUSLOGS(STARTTIME) values(to_date('2009-5-21 18:55:49','yyyy/mm/...
  • Python字符串匹配----6种方法的使用

    万次阅读 多人点赞 2019-12-17 14:21:16
    1. re.match 尝试从字符串的起始位置匹配一个模式,如果不是起始位置匹配成功的话,match()就返回none。 import re line="this hdr-biz 123 model server 456" pattern=r"123" matchObj = re.match( pattern, ...
  • 正则表达式匹配任意字符串

    万次阅读 2018-03-09 20:25:38
    ) 匹配所有字符串&lt;p class="num"&gt;9033&lt;/p&gt;如使用&lt;p class="(.*?)"&gt;9033&lt;/p&gt;会得到num但是如果带换行符会失效,如果需要匹配包括换行...
  • SQL 中字符串匹配的用法

    万次阅读 2018-01-17 11:32:13
    SQL中常用到字符串匹配。 1.like:找出满足给定条件的字符串; 格式:列名 [not] like '字符串'。 2.匹配规则: %:匹配一个或多个字符; _:匹配任意单个字符; escape:定义转义字符。 3.实例: 匹配‘张...
  • 正则匹配两个字符之间的字符串

    万次阅读 2018-09-05 10:39:04
    匹配两个字符串X与Y中间的字符串包含A与B:  表达式: X.*?Y(“.“表示任意字符,“?”表示匹配0个或多个)  示例: Xabab 结果: XababcdcY匹配两个字符串A与B中间的字符串包含A但是不包含B:  表达式: X.*?(?=Y)...
  • 匹配两个字符串A与B中间的字符串包含A与B: 表达式: A.*?B(“.“表示任意字符,“?”表示匹配0个或多个) 示例: Abaidu.comB 结果: Awww.apizl.comB 匹配两个字符串A与B中间的字符串包含A但是不包含B: ...
  • 几个高效的字符串匹配算法

    万次阅读 2017-03-12 14:49:04
    在写这篇之前,我一定要说,我讨厌KMP算法!!!所以我是不会讲解KMP算法的!!! 好了,开始。 ...创新之处是模式是从右向左进行比较。...第二步:模式从不匹配的那个字符开始,从右向左寻找匹配串中不匹配
  • select v.spid spid,v.appid appid,v.version version,v.newversion newversion,v.status status,v.createtime createtime from adc_spversionchangeapply v inner join adc_application a on a.id=v.appid w
1 2 3 4 5 ... 20
收藏数 820,906
精华内容 328,362
关键字:

字符串匹配