串与串的模式匹配

什么是串

• 线性存储的一组数据(默认是字符)
• 是线性表的一种特殊的应用，指的就是线性存储的一组数据
• 特殊操作集
  • 求串的长度
  • 比较两串是否相等
  • 两串相接
  • 求子串
  • 插入子串
  • 匹配子串
  • 删除子串

模式匹配

目标：

• 给定一段文本，从中找出某个指定的关键字。
• 例：从一本Thomas Love Peacock写于十九世纪的小说《Headlong Hall》中找到那个最长的单词
  • osseocarnisanguineoviscericartilaginonervomedullary
• 或者从古希腊喜剧《Assemblywomen》中找到一道菜的名字
  • Lopadotemachoselachogaleokranioleipsanodrimhypotrim
    matosilphioparaomelitokatakechymenokichlepikossyphoph
    attoperisteralektryonoptekephalliokigklopeleiolagoiosiraio baphetraganopterygon

实质：

• 给定一段文本：string=s(0)s(1)……s(n-1)
• 给定一个模式：pattern=p(0)p(1)……p(m-1)
• 求pattern在string中出现的位置
  • Position PatternMatch(char* string,char* pattern);

简单实现：

• 方法1:c的库函数strstr
  • char* strstr(char* string,char* pattern);
• 伪代码描述

#include<stdio.h>
#include<string.h>
typedef char*Position;
#define NotFound NULL
int main(){
    char string[]="This is a simple example.";
    char pattern[]="simple";
    Position p=strstr(string,pattern);
    if(p==NotFound)printf("Not Found.\n");
    else printf("%s\n",p);
    return 0;
}

• 时间复杂度分析：
• 假设string=“aaaaaaaaaaaaaaaaaaaaaaaaaaaaaa” 长度为n，
  pattern=“aab” 长度为m
• 在最坏情况下，子串要分别与主串中每个字符开头长度为m的子串进行匹配
• 每次匹配需比较m个字符，总共需要n数量级的匹配次数
  • $T=O(n*m)$

大师改进：

• 方法2:kMP(Knuth、Morris、Pratt)算法

• 时间复杂度：$T(n+m)$，通过对模式串的一个预处理，将时间复杂度减少到了一个线性的水平
• 例：string:…… a b c a b x y …… pattern:a b c a b c a
  • 在一次匹配当中发现子串的最后两个字符与模式串不符，匹配失败
  • 但是，在匹配中发现子串与模式串中的前5个字符是可以对应上的，因此可以将这些已知的信息再次利用
  • 同时观察发现，模式串中第1，2，3个字符与第4，5，6个字符是相同的，而前3个字符在上次匹配时是能够对应上的
  • 因此，下次匹配可以直接将模式串指针移动3个字符
• 算法核心：对模式串进行处理，得到match数组(一般也称next数组)
  • match(j)=满足p(0)……p(i)=p(j-1)……p(j)的i中最大那个
  • match(j)=-1 (如果这样的i不存在)
• match数组的实质：对模式串的第j个字符来说，是否存在从模式串第一个字符出发得到的子串与从第j-1个位置出发得到的子串相同的情况
  • 如果有的话，则match(j)取子串长度可能的最大值-1(前面子串结尾处的下标)
• 在上例中:

pattern	a	b	c	a	b	c	a	c	a	b
j	0	1	2	3	4	5	6	7	8	9
match	-1	-1	-1	0	1	2	3	-1	0	1

主体部分伪代码描述

#include<stdio.h>
#include<string.h>
typedef int Position;
#define NotFound -1
int main(){
    char string[]="This is a simple example.";
    char pattern[]="simple";
    Position p=KMP(string,pattern);
    if(p==NotFound)printf("Not Found.\n");
    else printf("%s\n",string+p);
    return 0;
}
Position KMP(char*string,char*pattern){
    int n=strlen(string);               //O(n)
    int m=strlen(pattern);              //O(m)
    int s,p,*match;
    if(n<m)return NotFound;
    match=(int*)malloc(sizeof(int)*m);
    BuildMatch(pattern,match);          //T(m)=O(m)
    s=p=0;
    while(s<n&&p<m){                    //O(n)
        if(string[s]==pattern[p]){
            s++;p++;
        }
        else if(p>0)p=match[p-1]+1;     //这里+1很重要，不然p=-1的时候就死循环了
        else s++;
    }
    return(p==m)?s-m:NotFOund;
}
这部分时间复杂度：T=O(n+m+T(m))

BuildMatch的实现

• 方法1：如果考虑采用逐个元素搜索最大子串的方法：for(j=0;j<m;j++)
  • 最大子串最坏情况下平均需要$O(m^2)$时间复杂度才能找到
  • m个元素总复杂度为$T(m)=O(m^3)$，因此这种方法完全无法接受

• 方法2：假设已经得到了j-1的match值
  • 对于j，只需直接与match[j-1]的下一个字符比较(子串开始处的下一个字符)
  • 如果相等，则match[j]=match[j-1]+1
    • 相等的话j的最大子串说明在j-1的最大子串的基础上+1即可，这里运用了动态规划的思想
• 如果不相等就与match[match[j-1]]+1位置的字符比对(不相等的再继续往前回溯，直到第0个match值一定为-1)
  • match[match[j-1]]+1代表当前字符前一个字符的next值对应字符的下一个位置
• if(pattern[match[j-1]+1]==pattern[j])match[j]=match[j-1]+1;

void BuildMatch(char*pattern,int*match){
    int i,j;
    int m=strlen(pattern);
    match[0]=-1;
    for(j=1;j<m;j++){
        i=match[j-1];
        while((i>=0)&&(pattern[i+1]!=pattern[j]))
        i=match[i];                 //由于i回退的总次数不会超过i增加的总次数(要先有match[j-1]才可能回退)
        if(pattern[i+1]==pattern[j])
        match[j]=i+1;
        else match[j]=-1;               //因此T(m)是关于m的线性复杂度即T(m)=O(m)
    }
}  

KMP算法演示

// 引自浙江大学mooc数据结构课程
#include <stdio.h>
#include <string.h> 
#include <stdlib.h>

typedef int Position;
#define NotFound -1

void BuildMatch( char *pattern, int *match )
{
	Position i, j;
	int m = strlen(pattern);
	match[0] = -1;

	for ( j=1; j<m; j++ ) {
		i = match[j-1];
		while ( (i>=0) && (pattern[i+1]!=pattern[j]) )
			i = match[i];
		if ( pattern[i+1]==pattern[j] )
		     match[j] = i+1;
		else match[j] = -1;
	}
}

Position KMP( char *string, char *pattern )
{
	int n = strlen(string);
	int m = strlen(pattern);
	Position s, p, *match;

	if ( n < m ) return NotFound;
	match = (Position *)malloc(sizeof(Position) * m);
	BuildMatch(pattern, match);
	s = p = 0;
	while ( s<n && p<m ) {
		if ( string[s]==pattern[p] ) {
			s++; p++;
		}
		else if (p>0) p = match[p-1]+1;
		else s++;
	}
	return ( p==m )? (s-m) : NotFound;
}

int main()
{
	char string[] = "This is a simple example.";
	char pattern[] = "simple";
	Position p = KMP(string, pattern);
	if (p==NotFound) printf("Not Found.\n");
	else printf("%s\n", string+p);
	return 0;
}