什么是串

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

模式匹配

目标:

  • 给定一段文本,从中找出某个指定的关键字。
  • 例:从一本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(nm)T=O(n*m)

大师改进:

  • 方法2:kMP(Knuth、Morris、Pratt)算法
  • 时间复杂度:T(n+m)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(m2)O(m^2)时间复杂度才能找到
    • m个元素总复杂度为T(m)=O(m3)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;
}