顺序队列中的溢出现象

  ① “下溢”现象
 当队列为空时,做出队运算产生的溢出现象。“下溢”是正常现象,常用作程序控制转移的条件。
  ② “真上溢”现象
 当队列满时,做进栈运算产生空间溢出的现象。“真上溢”是一种出错状态,应设法避免。
  ③ “假上溢”现象
  由于入队和出队操作中,头尾指针只增加不减小,致使被删元素的空间永远无法重新利用。当队列中实际的元素个数远远小于向量空间的规模时,也可能由于尾指针已超越向量空间的上界而不能做入队操作。该现象称为”假上溢”现象。

 

【例】假设下述操作序列作用在初始为空的顺序队列上:

EnQueue,DeQueue,EnQueue,DeQueue,…

尽管在任何时刻,队列元素的个数均不超过1,但是只要该序列足够长,事先定义的向量空间无论多大均会产生指针越界错误。

通过中序和后序快速画出二叉树

很简单。这也是个递归过程。
知道后序,就能找到“根”,是最后一个节点。
知道“根”节点,就好办了,从中序中把根结点找到,它左边是左子树的中序,
右边是右子树的中序,知道这两子树的中序,就能从后序中,把左子序、右子树
找出来(据中序的左、右子树的结点数)。
这样,根节点找出来了,左子数的后序、中序就分离出来了,右子数也分离出来了,
这个问题,就化成两个新树的问题。同样的办法如此,就是递归成两个子树的新问题。
如果用程序,一样用递归就做出来了。

实例:

中序:dgbaechf        //左根右
后序:gdbehfca     //左右根
(1)确定根
         由后序得
        中序:(dgb)a(echf)   后序:(gdb)(ehfc)a  
 (2)确定左节点
          由上已知,左节点没有有节点
  (3)确定右节点
           中序【(e)c(hf)】  后序:【(e)(hf)c】  
     确定整棵树为
---------a--------
------b-----c-----
---d------e---f---
-g--------------h-

顺序表的类型定义

1.先介绍一下顺序表:
(1) 顺序存储方法
  即把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里的方法。
(2) 顺序表(Sequential List)
  用顺序存储方法存储的线性表简称为顺序表(Sequential List)。

2.顺序表类型定义

  #define ListSize 100 //表空间的大小可根据实际需要而定,这里假设为100
  typedef int DataType; //DataType的类型可根据实际情况而定,这里假设为int
  typedef struct {
      DataType data[ListSize];//向量data用于存放表结点
      int length;//当前的表长度
     }SeqList;
typedef struct
{
	int *elem;
	int length;
	int listsize;
}SqList;

上者对于初学者更容易理解,下者更优。

注意:
  ① 用向量这种顺序存储的数组类型存储线性表的元素外,顺序表还应该用一个变量来表示线性表的长度属性,因此用结构类型来定义顺序表类型。
 ② 存放线性表结点的向量空间的大小ListSize应仔细选值,使其既能满足表结点的数目动态增加的需求,又不致于预先定义过大而浪费存储空间。
 ③ 由于C语言中向量的下标从0开始,所以若L是SeqList类型的顺序表,则线性表的开始结点a1和终端结点an分别存储在L.data[0]和L.Data[L.length-1]中。
 ④ 若L是SeqList类型的指针变量,则a1和an分别存储在L->data[0]和L->data[L->length-1]中。

求字符串中互异的非平凡子串

问题:数据结构问题,设S是一个长度为n的字符串,其中字符各不相同,则S中的互异非平凡子串(非空切不同于本身)

实例解释:

比如S字串为”abcdefg”,长度为7。则S中的包含的互不相同的字串有如下一些:

1.长度为6的个数为2:”abcdef”和”bcdefg”

2.长度为5的个数为3:”abcde”,”bcdef”,”cdefg”

。。。

6.长度为1的个数为7:”a”,”b”,”c”,”d”,”e”,”f”,”g”,个数总和就是2+3+4+5+6+7 = (1+2+3+..+7) – 1 = 7x(7+1)/2 – 1.

其中:
1+2+3+…+n = (1+n) + (2+(n-1)) + (3+(n-2)) + …(首尾两项相加的和都是n+1,共 n/2个)
= n(n+1)/2

补充:上面的公式还需要减1,因为只需要从2累加到n,字符串本身不算。

也可以这样想:(n-1)+(n-1)+(n-2)+…+2+1

内部排序之希尔排序

排序思想:

希尔排序也称“缩小增量排序”,属于插入排序类方法。

首先确定间隔值d( d的取值将直接影响 shell排序的效率 ),根据d将整个待排序记录序列分割成为若干子序列(即分别把那些位置相隔为d 的元素看作一个子序列)分别进行直接插入排序,然后减小d值,重复上述过程,直到d<1为止。

待整个序列中的记录“基本有序”时再对全体记录进行一次直接插入排序。

 

希尔排序算法

void ShellInsert(SqList &L,int dk)
{//一趟shell排序
	for(i=dk+1;i<=L.length;++i)
		if  LT(L.r[i].key,L.r[i-dk].key)
		{
			L.r[0]=L.r[i];
			for(j=i-dk;j>0 && LT(L.r[0].key,L.r[j].key);j-=dk)
				L.r[j+dk]=L.r[j];
			L.r[j+dk]=L.r[0];
		}
}//SellInsert
void ShellSort(SqList &L,int dlta[],int t)
{
	for(k=0;k<t;++k)
		ShellInsert(L,dlta[k]);
}//ShellSort

希尔排序分析:

不稳定的排序方法

时间复杂度与增量序列dlta[]相关,约为n1.3(阅读教材P272)

空间复杂度O(1)

 

希尔排序特点:

子序列的构成不是简单的“逐段分割”,而是将相隔某个增量的记录组成一个子序列

希尔排序可提高排序速度,因为:

1.分组后n值减小,n²更小,而T(n)=O(n²),所以T(n)从总体上看是减小了

2.关键字较小的记录跳跃式前移,在进行最后一趟增量为1的插入排序时,序列已基本有序

增量序列取法:

1.无除1以外的公因子

2.最后一个增量值必须为1

 

内部排序之堆排序

堆排序算法:

void HeapAdjust(SqList &L,int s,int m)
{
	int j,rc;
	rc=L.elem[s];
	for(j=2*s;j<=m;j*=2)
	{
		if(jL.elem[j])
			break;
		L.elem[s]=L.elem[j];
		s=j;
	}
	L.elem[s]=rc;
}

 

void HeapSort(SqList &L)
{
	int i,temp;
	for(i=L.length/2;i>0;i--)
		HeapAdjust(L,i,L.length);
	for(i=L.length;i>=1;i--)
	{
		Load_Sq(L);
		temp=L.elem[1];
		L.elem[1]=L.elem[i];
		L.elem[i]=temp;
		HeapAdjust(L,1,i-1);
	}
}

 

 

堆排序方法特点: (考虑与希尔排序对比)

时间复杂度O(nlogn)

空间复杂度O(1)

不稳定排序

运行时间主要耗费在建初始堆和调整堆上,适用于大批量数据的部分排序(如1000个数据取5个关键字最大的数。)

以下算法转自CSDN博客(堆排序(大顶堆->升序)):

#include   
#include   
  
/* 堆排序 */  
void HeapAdjust(int a[],int index,int n)  
{   //注意规定a[0]不存放元素,当做缓存用  
    int i,father = index,son;  
  
    a[0] = a[index];  
    for(son=2*father; son<=n; son*=2)//比较子节点  
    {  
        if(son a[son])son++;//右节点更大  
        if(a[son] < a[0] )break;//不需要继续了  
  
        a[father] = a[son];//大的上提  
        father = son;  
    }  
    a[father] = a[0];  
}  
void HeapSort(int a[],int n)  
{   //注意规定a[0]不存放元素,当做缓存用  
    int i;  
    for(i=n/2; i>0; i--)//从最后一个非叶节点开始从下往上建立大顶堆  
        HeapAdjust(a,i,n);  
    for(i=n; i>1; i--)//不断抽取堆顶,调整  
    {  
        a[0] = a[i];  
        a[i] = a[1];  
        a[1] = a[0];  
        HeapAdjust(a,1,i-1);  
    }  
}  
int main(int argc, char *argv[])  
{  
    int a[] = {-1,4,5,3,2,9,8,1,7,6,0};  
    int i;  
  
    HeapSort(a,10);  
    for(i=1; i<=10; i++)printf("%d\t",a[i]);  
    printf("\n");  
    return 1;  
}

关于堆排序选择大顶堆还是小顶堆的评论:

建大顶,小顶都可以,假如建大顶堆,每次选出来的都是最大的,如果要求从小到大排,就把选来的元素放到最后就好了,如果要求从大到小排,就放到最前。不过习惯上,还是大顶堆,从大到小排,小顶堆,从小到大排。

建立大顶堆可以保证顶是最大的,把他和堆的最后一个元对调就实现了从最后一个元最大;以此类推。
我感觉严书上讲得过于简洁了,堆排序第一步要建立堆,第二步才是对堆排序。

简单选择排序算法

void SelectSort (SqList &L)
{
	for(i=1;i<L.length;++i)
	{
		j=SelectMinKey(L,i);
			if(i!=j)L.r[i]←→L.r[j];
	}
}//SelectSort

 

简单选择排序:

时间复杂度O(n2) (与待排记录的初始状态无关

记录移动的操作次数

最好情况:0

最坏情况:3(n-1)

比较次数:(n*n-n)/2

空间复杂度为O(1)

如何快速看出模式串的next数组的值

直接上实例:

求模式串 P = ‘abaabcac’的 next 函数值序列。

abaabcac

01122312

前两个字母next序列分别为01,直接写上

第三个”a” 时,它前一个字母为b,从头开始字母为a, a!=b所以为1

第四个”a” 时,前字母为a,从头开始字母为a,a=a,所以值为1+1=2(相等时为串长加1)

第五个”b”,前个字母为a,从头开始a,a=a,为2

第六个”c”,前个字母为b,再往前是a,ab,从头开始ab串,ab=ab,因此值为2+1=3

第七个字母为”a”,前个字母为c,与从头开始的第一个字母不相等,所以为1

第八个为”c”,前个字母为a,与开始第一个字母相等,因此为2

 

其他答案:

模式串P = 'abaabcac'的next函数值序列为  -1 0 0 1 1 2 0 1

关于线性结构的概念

数据结构课程中数据的逻辑结构分为线性结构和非线性结构。

对于数据结构课程而言,简单地说,线性结构是n个数据元素的有序(次序)集合。它有四个基本特征:

1.集合中必存在唯一的一个”第一个元素”;

2.集合中必存在唯一的一个”最后的元素”;

3.除最后元素之外,其它数据元素均有唯一的”后继”;

4.除第一元素之外,其它数据元素均有唯一的”前驱”。

数据结构中线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。

如(a1,a2,a3,…..,an),a1为第一个元素,an为最后一个元素,此集合极为一个线性结构的集合。

相对应于线性结构,非线性结构的逻辑特征是一个结点元素可能对应多个直接前驱和多个后驱。

常用的线性结构有:线性表,栈,队列,双队列,数组,串。

关于广义表,是一种非线性的数据结构。

常见的非线性结构有:树(二叉树等),图(网等)。

稀疏矩阵也是非线性结构。

KMP算法详解(转)

KMP算法详解(转)——这篇文章介绍kmp算法十分详实,故转载给大家交流与学习。

引记

此前一天,一位MS的朋友邀我一起去与他讨论快速排序,红黑树,字典树,B树、后缀树,包括KMP算法,唯独在讲解KMP算法的时候,言语磕磕碰碰,我想,原因有二:1、博客内的东西不常回顾,忘了不少;2、便是我对KMP算法的理解还不够彻底,自不用说讲解自如,运用自如了。所以,特再写本篇文章。由于此前,个人已经写过关于KMP算法的两篇文章,所以,本文名为:KMP算法之总结篇。

本文分为如下六个部分:

  1. 第一部分、再次回顾普通的BF算法与KMP算法各自的时间复杂度,并两相对照各自的匹配原理;
  2. 第二部分、通过我此前第二篇文章的引用,用图从头到尾详细阐述KMP算法中的next数组求法,并运用求得的next数组写出KMP算法的源码;
  3. 第三部分、KMP算法的两种实现,代码实现一是根据本人关于KMP算法的第二篇文章所写,代码实现二是根据本人的关于KMP算法的第一篇文章所写;
  4. 第四部分、测试,分别对第三部分的两种实现中next数组的求法进行测试,挖掘其区别之所在;
  5. 第五部分、KMP完整准确源码,给出KMP算法的准确的完整源码;
  6. 第六步份、一眼看出字符串的next数组各值,通过几个例子,让读者能根据字符串本身一眼判断出其next数组各值。

力求让此文彻底让读者洞穿此KMP算法,所有原理,来龙去脉,让读者搞个通通透透(注意,本文中第二部分及第三部分的代码实现一的字符串下标i 从0开始计算,其它部分如第三部分的代码实现二,第五部分,和第六部分的字符串下标i 皆是从1开始的)。

在看本文之前,你心中如若对前缀和后缀这个两个概念有自己的理解,便最好了。有些东西比如此KMP算法需要我们反复思考,反复求解才行。个人写的关于KMP算法的第二篇文章为:六(续)、从KMP算法一步一步谈到BM算法;第一篇为:六、教你初步了解KMP算法、updated(文末链接)。ok,若有任何问题,恳请不吝指正。多谢。

第一部分、KMP算法初解

1、普通字符串匹配BF算法与KMP算法的时间复杂度比较

KMP算法是一种线性时间复杂的字符串匹配算法,它是对BF算法(Brute-Force,最基本的字符串匹配算法的)改进。对于给的原始串S和模式串P,需要从字符串S中找到字符串P出现的位置的索引。

BF算法的时间复杂度O(strlen(S) * strlen(T)),空间复杂度O(1)。

KMP算法的时间复杂度O(strlen(S) + strlen(T)),空间复杂度O(strlen(T))。

2、BF算法与KMP算法的区别

假设现在S串匹配到i位置,T串匹配到j位置。那么总的来说,两种算法的主要区别在于失配的情况下,对的值做的处理:

BF算法中,如果当前字符匹配成功,即s[i+j] == T[j],令j++,继续匹配下一个字符;如果失配,即S[i + j] != T[j],需要让i++,并且j= 0,即每次匹配失败的情况下,模式串T相对于原始串S向右移动了一位。

而KMP算法中,如果当前字符匹配成功,即S[i]==T[j],令i++,j++,继续匹配下一个字符;如果匹配失败,即S[i] != T[j],需要保持i不变,并且让j = next[j],这里next[j] <=j -1,即模式串T相对于原始串S向右移动了至少1位(移动的实际位数j – next[j]  >=1),

同时移动之后,i之前的部分(即S[i-j+1 ~ i-1]),和j=next[j]之前的部分(即T[0 ~ j-2])仍然相等。显然,相对于BF算法来说,KMP移动更多的位数,起到了一个加速的作用! (失配的特殊情形,令j=next[j]导致j==0的时候,需要将i ++,否则此时没有移动模式串)。

3、BF算法为什么要回溯

首先说一下为什么BF算法要回溯。如下两字符串匹配(恰如上面所述:BF算法中,如果当前字符匹配成功,即s[i+j] == T[j],令j++,继续匹配下一个字符):

i+j(j随T中的j++变,而动)

S:aaaacefghij

j++

T:aaac

如果不回溯的话就是从下一位开始比起:

aaaacefghij

aaac

看到上面红颜色的没,如果不回溯的话,那么从a 的下一位c 比起。然而下述这种情况就漏了(正确的做法当然是要回溯:如果失配,即S[i + j] != T[j],需要让i++,并且j= 0):

aaaacefghij

aaac

    所以,BF算法要回溯,其代码如下:

  1. int Index(SString S, SString T, int pos) {
  2.    //返回T在S中第pos个字符之后的位置
  3.    i=pos; j=1;k=0;
  4.   while ( i< = S[0] && j< = T[0] ) {
  5.       if (S[i+k] = = T[j] ) {++k;  ++j;}   //继续比较后续字符
  6.       else {i=i+1;   j=1; k=0;}      //指针回溯到 下一首位,重新开始
  7.   }
  8.   if(j>T[0]) return i;          //子串结束,说明匹配成功
  9.   else return  0;
  10. }//Index

不过,也有特殊情况可以不回溯,如下:
abcdefghij(主串)
abcdefg(模式串)
即(模式串)没有相同的才不需要回溯。
4、KMP 算法思想
普通的字符串匹配算法必须要回溯。但回溯就影响了效率,回溯是由T串本身的性质决定的,是因为T串本身有前后’部分匹配’的性质。像上面所说如果主串为abcdef这样的,大没有回溯的必要。

改进的地方也就是这里,我们从T串本身出发,事先就找准了T自身前后部分匹配的位置,那就可以改进算法。

如果不用回溯,那模式串下一个位置从哪里开始呢?

还是上面那个例子,T(模式串)为ababc,如果c失配,那就可以往前移到aba最后一个a的位置,像这样:

…ababd…

   ababc

    ->ababc

这样i不用回溯,j跳到前2个位置,继续匹配的过程,这就是KMP算法所在。这个当T[j]失配后,j 应该往前跳的值就是j的next值,它是由T串本身固有决定的,与S串(主串)无关
5、next数组的含义

重点来了。下面解释一下next数组的含义,这个也是KMP算法中比较不好理解的一点。

令原始串为: S[i],其中0<=i<=n;模式串为: T[j],其中0<=j<=m。

假设目前匹配到如下位置

S0,S1,S2,…,Si-j,Si-j+1……………,Si-1, Si, Si+1,….,Sn

T0,T1,…………………,Tj-1, Tj, ……….

S和T的绿色部分匹配成功,恰好到Si和Tj的时候失配,如果要保持i不变,同时达到让模式串T相对于原始串S右移的话,可以更新j的值,让Si和新的Tj进行匹配,假设新的j用next[j]表示,即让Si和next[j]匹配,显然新的j值要小于之前的j值,模式串才会是右移的效果,也就是说应该有next[j] <= j -1。那新的j值也就是next[j]应该是多少呢?我们观察如下的匹配:

1)如果模式串右移1位(从简单的思考起,移动一位会怎么样),即next[j] = j – 1, 即让蓝色的Si和Tj-1匹配(注:省略号为未匹配部分)

S0,S1,S2,…,Si-j,Si-j+1……………,Si-1, Si, Si+1,….,Sn

T0,T1,…………………,Tj-1, Tj, ………. (T的划线部分和S划线部分相等【1】)

T0,T1,……………..Tj-2,Tj-1, ……. (移动后的T的划线部分和S的划线部分相等【2】)

根据【1】【2】可以知道当next[j] =j -1,即模式串右移一位的时候,有T[0 ~ j-2] == T[1 ~ j-1],而这两部分恰好是字符串T[0 ~j-1]的前缀和后缀,也就是说next[j]的值取决于模式串T中j前面部分的前缀和后缀相等部分的长度(好好揣摩这两个关键字概念:前缀、后缀,或者再想想,我的上一篇文章,从Trie树谈到后缀树中,后缀树的概念)。

2)如果模式串右移2位,即next[j] = j – 2, 即让蓝色的Si和Tj-2匹配

S0,S1,…,Si-j,Si-j+1,Si-j+2……………,Si-1, Si, Si+1,….,Sn

T0,T1,T2,…………………,Tj-1, Tj, ……….(T的划线部分和S划线部分相等【3】)

T0,T1,……………,Tj-3,Tj-2,………(移动后的T的划线部分和S的划线部分相等【4】)

同样根据【3】【4】可以知道当next[j] =j -2,即模式串右移两位的时候,有T[0 ~ j-3] == T[2 ~ j-1]。而这两部分也恰好是字符串T[0 ~j-1]的前缀和后缀,也就是说next[j]的值取决于模式串T中j前面部分的前缀和后缀相等部分的长度。

3)依次类推,可以得到如下结论:当发生失配的情况下,j的新值next[j]取决于模式串中T[0 ~ j-1]中前缀和后缀相等部分的长度, 并且next[j]恰好等于这个最大长度

为此,请再允许我引用上文中的一段原文:“KMP算法中,如果当前字符匹配成功,即S[i]==T[j],令i++,j++,继续匹配下一个字符;如果匹配失败,即S[i] != T[j],需要保持i不变,并且让j = next[j],这里next[j] <=j -1,即模式串T相对于原始串S向右移动了至少1位(移动的实际位数j – next[j]  >=1),

同时移动之后,i之前的部分(即S[i-j+1 ~ i-1]),和j=next[j]之前的部分(即T[0 ~ j-2])仍然相等。显然,相对于BF算法来说,KMP移动更多的位数,起到了一个加速的作用! (失配的特殊情形,令j=next[j]导致j==0的时候,需要将i ++,否则此时没有移动模式串)。”

于此,也就不难理解了我的关于KMP算法的第二篇文章之中:“当匹配到S[i] != P[j]的时候有 S[i-j…i-1] = P[0…j-1]. 如果下面用j_next去匹配,则有P[0…j_next-1] = S[i-j_next…i-1] = P[j-j_next…j-1]。此过程如下图3-1所示。

当匹配到S[i] != P[j]时,S[i-j…i-1] = P[0…j-1]:

S: 0 … i-j … i-1 i …

P:       0 …   j-1 j …

如果下面用j_next去匹配,则有P[0…j_next-1] = S[i-j_next…i-1] = P[j-j_next…j-1]。
所以在P中有如下匹配关系(获得这个匹配关系的意义是用来求next数组):

P: 0 … j-j_next  .…j-1_    …

P:        0    … .j_next-1 …

所以,根据上面两个步骤,推出下一匹配位置j_next:

S: 0 … i-j … i-j_next …   i-1      i …

P:                   0   … j_next-1 j_next …

图3-1 求j-next(最大的值)的三个步骤

下面,我们用变量k来代表求得的j_next的最大值,即k表示这S[i]、P[j]不匹配时P中下一个用来匹配的位置,使得P[0…k-1] = P[j-k…j-1],而我们要尽量找到这个k的最大值。”。

根据上文的【1】与【2】的匹配情况,可得第二篇文章之中所谓的k=1(如aaaa的形式),根据上文的【3】与【4】的匹配情况,k=2(如abab的形式)。

所以,归根究底,KMP算法的本质便是:针对待匹配的模式串的特点,判断它是否有重复的字符,从而找到它的前缀与后缀,进而求出相应的Next数组,最终根据Next数组而进行KMP匹配。接下来,进入本文的第二部分。

第二部分、next数组求法的来龙去脉与KMP算法的源码

本部分引自个人此前的关于KMP算法的第二篇文章:六之续、由KMP算法谈到BM算法。前面,我们已经知道即不能让P[j]=P[next[j]]成立成立。不能再出现上面那样的情况啊!即不能有这种情况出现:P[3]=b,而竟也有P[next[3]]=P[1]=b。

正如在第二篇文章中,所提到的那样:“这里读者理解可能有困难的是因为文中,时而next,时而nextval,把他们的思维搞混乱了。其实next用于表达数组索引,而nextval专用于表达next数组索引下的具体各值,区别细微。至于文中说不允许P=P[next[j] ]出现,是因为已经有P=b与S匹配败,而P[next]=P1=b,若再拿P[1]=b去与S匹配则必败。”–六之续、由KMP算法谈到BM算法。

又恰恰如上文中所述:“模式串T相对于原始串S向右移动了至少1位(移动的实际位数j – next[j]  >=1)”。

ok,求next数组的get_nextval函数正确代码如下:

  1. //代码4-1
  2. //修正后的求next数组各值的函数代码
  3. void get_nextval(char const* ptrn, int plen, int* nextval)
  4. {
  5.     int i = 0;
  6.     nextval[i] = -1;
  7.     int j = -1;
  8.     while( i < plen-1 )
  9.     {
  10.         if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分
  11.         {
  12.             ++i;
  13.             ++j;
  14.             //修正的地方就发生下面这4行
  15.             if( ptrn[i] != ptrn[j] ) //++i,++j之后,再次判断ptrn[i]与ptrn[j]的关系
  16.                 nextval[i] = j;      //之前的错误解法就在于整个判断只有这一句。
  17.             else
  18.                 nextval[i] = nextval[j];
  19.         }
  20.         else                                 //循环的else部分
  21.             j = nextval[j];
  22.     }
  23. }

    举个例子,举例说明下上述求next数组的方法。
S a b a b a b c
P a b a b c
S[4] != P[4]
那么下一个和S[4]匹配的位置是k=2(也即P[next[4]])。此处的k=2也再次佐证了上文第3节开头处关于为了找到下一个匹配的位置时k的求法。上面的主串与模式串开头4个字符都是“abab”,所以,匹配失效后下一个匹配的位置直接跳两步继续进行匹配。
S a b a b a b c
P      a b a b c
匹配成功

P的next数组值分别为-1 0 -1 0 2

next数组各值怎么求出来的呢?分以下五步:

  1. 初始化:i=0,j=-1,nextval[0] = -1。由于j == -1,进入上述循环的if部分,++i得i=1,++j得j=0,且ptrn[i] != ptrn[j](即a!=b)),所以得到第二个next值即nextval[1] = 0;;
  2. i=1,j=0,进入循环esle部分,j=nextval[j]=nextval[0]=-1;
  3. 进入循环的if部分,++i,++j,i=2,j=0,因为ptrn[i]=ptrn[j]=a,所以nextval[2]=nextval[0]=-1;
  4. i=2, j=0, 由于ptrn[i]=ptrn[j],再次进入循环if部分,所以++i=3,++j=1,因为ptrn[i]=ptrn[j]=b,所以nextval[3]=nextval[1]=0;
  5. i=3,j=1,由于ptrn[i]=ptrn[j]=b,所以++i=4,++j=2,退出循环。

这样上例中模式串的next数组各值最终应该为:

 

图4-1 正确的next数组各值
next数组求解的具体过程如下:
    初始化:nextval[0] = -1,我们得到第一个next值即-1.

 

图4-2 初始化第一个next值即-1

i = 0,j = -1,由于j == -1,进入上述循环的if部分,++i得i=1,++j得j=0,且ptrn[i] != ptrn[j](即a!=b)),所以得到第二个next值即nextval[1] = 0;

 

图4-3 第二个next值0

上面我们已经得到,i= 1,j = 0,由于不满足条件j == -1 || ptrn[i] == ptrn[j],所以进入循环的esle部分,得j = nextval[j] = -1;此时,仍满足循环条件,由于i = 1,j = -1,因为j == -1,再次进入循环的if部分,++i得i=2,++j得j=0,由于ptrn[i] == ptrn[j](即ptrn[2]=ptrn[0],也就是说第1个元素和第三个元素都是a),所以进入循环if部分内嵌的else部分,得到nextval[2] = nextval[0] = -1;

 

图4-4 第三个next数组元素值-1

i = 2,j = 0,由于ptrn[i] == ptrn[j],进入if部分,++i得i=3,++j得j=1,所以ptrn[i] == ptrn[j](ptrn[3]==ptrn[1],也就是说第2个元素和第4个元素都是b),所以进入循环if部分内嵌的else部分,得到nextval[3] = nextval[1] = 0;

 

图4-5 第四个数组元素值0
如果你还是没有弄懂上述过程是怎么一回事,请现在拿出一张纸和一支笔出来,一步一步的画下上述过程。相信我,把图画出来了之后,你一定能明白它的。
然后,我留一个问题给读者,为什么上述的next数组要那么求?有什么原理么?

提示:我们从上述字符串abab 各字符的next值-1 0 -1 0,可以看出来,根据求得的next数组值,偷用前缀、后缀的概念,一定可以判断出在abab之中,前缀和后缀相同,即都是ab,反过来,如果一个字符串的前缀和后缀相同,那么根据前缀和后缀依次求得的next各值也是相同的。

  • 5、利用求得的next数组各值运用Kmp算法

Ok,next数组各值已经求得,万事俱备,东风也不欠了。接下来,咱们就要应用求得的next值,应用KMP算法来匹配字符串了。还记得KMP算法是怎么一回事吗?容我再次引用下之前的KMP算法的代码,如下:

  1. //代码5-1
  2. //int kmp_seach(char const*, int, char const*, int, int const*, int pos)  KMP模式匹配函数
  3. //输入:src, slen主串
  4. //输入:patn, plen模式串
  5. //输入:nextval KMP算法中的next函数值数组
  6. int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
  7. {
  8.     int i = pos;
  9.     int j = 0;
  10.     while ( i < slen && j < plen )
  11.     {
  12.         if( j == -1 || src[i] == patn[j] )
  13.         {
  14.             ++i;
  15.             ++j;
  16.         }
  17.         else
  18.         {
  19.             j = nextval[j];
  20.             //当匹配失败的时候直接用p[j_next]与s[i]比较,
  21.             //下面阐述怎么求这个值,即匹配失效后下一次匹配的位置
  22.         }
  23.     }
  24.     if( j >= plen )
  25.         return i-plen;
  26.     else
  27.         return -1;
  28. }

我们上面已经求得的next值,如下:

 

图5-1 求得的正确的next数组元素各值

以下是匹配过程,分三步:
第一步:主串和模式串如下,S[3]与P[3]匹配失败。

 

图5-2 第一步,S[3]与P[3]匹配失败
第二步:S[3]保持不变,P的下一个匹配位置是P[next[3]],而next[3]=0,所以P[next[3]]=P[0],即P[0]与S[3]匹配。在P[0]与S[3]处匹配失败。

 

图5-3 第二步,在P[0]与S[3]处匹配失败

第三步:与上文中第3小节末的情况一致。由于上述第三步中,P[0]与S[3]还是不匹配。此时i=3,j=nextval[0]=-1,由于满足条件j==-1,所以进入循环的if部分,++i=4,++j=0,即主串指针下移一个位置,从P[0]与S[4]处开始匹配。最后j==plen,跳出循环,输出结果i-plen=4(即字串第一次出现的位置),匹配成功,算法结束。

 

图5-4 第三步,匹配成功,算法结束
所以,综上,总结上述三步为:

  1. 开始匹配,直到P[3]!=S[3],匹配失败;
  2. nextval[3]=0,所以P[0]继续与S[3]匹配,再次匹配失败;
  3. nextval[0]=-1,满足循环if部分条件j==-1,所以,++i,++j,主串指针下移一个位置,从P[0]与S[4]处开始匹配,最后j==plen,跳出循环,输出结果i-plen=4,算法结束。

第三部分、KMP算法的两种实现

代码实现一:

根据上文中第二部分内容的解析,完整写出KMP算法的代码已经不是难事了,如下:

  1. //copyright@2011 binghu and july
  2. #include ”StdAfx.h”
  3. #include <string>
  4. #include <iostream>
  5. using namespace std;
  6. //代码4-1
  7. //修正后的求next数组各值的函数代码
  8. void get_nextval(char const* ptrn, int plen, int* nextval)
  9. {
  10.     int i = 0;  //注,此处与下文的代码实现二不同的是,i是从0开始的(代码实现二i从1开始)
  11.     nextval[i] = -1;
  12.     int j = -1;
  13.     while( i < plen-1 )
  14.     {
  15.         if( j == -1 || ptrn[i] == ptrn[j] )   //循环的if部分
  16.         {
  17.             ++i;
  18.             ++j;
  19.             //修正的地方就发生下面这4行
  20.             if( ptrn[i] != ptrn[j] ) //++i,++j之后,再次判断ptrn[i]与ptrn[j]的关系
  21.                 nextval[i] = j;      //之前的错误解法就在于整个判断只有这一句。
  22.             else
  23.                 nextval[i] = nextval[j];
  24.         }
  25.         else                                 //循环的else部分
  26.             j = nextval[j];
  27.     }
  28. }
  29. void print_progress(char const* src, int src_index, char const* pstr, int pstr_index)
  30. {
  31.     cout<<src_index<<”\t”<<src<<endl;
  32.     cout<<pstr_index<<”\t”;
  33.     for( int i = 0; i < src_index-pstr_index; ++i )
  34.         cout<<” ”;
  35.     cout<<pstr<<endl;
  36.     cout<<endl;
  37. }
  38. //代码5-1
  39. //int kmp_seach(char const*, int, char const*, int, int const*, int pos)  KMP模式匹配函数
  40. //输入:src, slen主串
  41. //输入:patn, plen模式串
  42. //输入:nextval KMP算法中的next函数值数组
  43. int kmp_search(char const* src, int slen, char const* patn, int plen, int const* nextval, int pos)
  44. {
  45.     int i = pos;
  46.     int j = 0;
  47.     while ( i < slen && j < plen )
  48.     {
  49.         if( j == -1 || src[i] == patn[j] )
  50.         {
  51.             ++i;
  52.             ++j;
  53.         }
  54.         else
  55.         {
  56.             j = nextval[j];
  57.             //当匹配失败的时候直接用p[j_next]与s[i]比较,
  58.             //下面阐述怎么求这个值,即匹配失效后下一次匹配的位置
  59.         }
  60.     }
  61.     if( j >= plen )
  62.         return i-plen;
  63.     else
  64.         return -1;
  65. }
  66. int   main()
  67. {
  68.     std::string src = ”aabcabcebafabcabceabcaefabcacdabcab”;
  69.     std::string prn = ”abac”;
  70.     int* nextval = new int[prn.size()];
  71.     //int* next = new int[prn.size()];
  72.     get_nextval(prn.data(), prn.size(), nextval);
  73.     //get_next(prn.data(), prn.size(), next);
  74.     for( int i = 0; i < prn.size(); ++i )
  75.         cout<<nextval[i]<<”\t”;
  76.     cout<<endl;
  77.     cout<<”result sub str: ”<<src.substr( kmp_search(src.data(), src.size(), prn.data(), prn.size(), nextval, 0) )<<endl;
  78.     system(“pause”);
  79.     delete[] nextval;
  80.     return 0;
  81. }

运行结果,如下图所示:

 

代码实现二

再给出代码实现二之前,让我们再次回顾下关于KMP算法的第一篇文章中的部分内容:

第二节、KMP算法

2.1、 覆盖函数(overlay_function)

覆盖函数所表征的是pattern本身的性质,可以让为其表征的是pattern从左开始的所有连续子串的自我覆盖程度。比如如下的字串,abaabcaba

可能上面的图令读者理解起来还是不那么清晰易懂,其实很简单,针对字符串abaabcaba

a(-1) b(-1)a(0) a(0) b(1) c(-1) a(0) b(1)a(2)

解释:

  1. 初始化为-1
  2. b与a不同为-1
  3. 与第一个字符a相同为0
  4. 还是a为0
  5. 后缀ab与前缀ab两个字符相同为1
  6. 前面并无前缀c为-1
  7. 与第一个字符同为0
  8. 后缀ab前缀ab为1
  9. 前缀aba后缀aba为2

由于计数是从0始的,因此覆盖函数的值为0说明有1个匹配,对于从0还是从来开始计数是偏好问题,具体请自行调整,其中-1表示没有覆盖,那么何为覆盖呢,下面比较数学的来看一下定义,比如对于序列

 

  a0a1…aj-1 aj

 

要找到一个k,使它满足

a0a1…ak-1ak=aj-kaj-k+1…aj-1aj

而没有更大的k满足这个条件,就是说要找到尽可能大k,使pattern前k字符与后k字符相匹配,k要尽可能的大,原因是如果有比较大的k存在。

但若我们选择较小的满足条件的k,那么当失配时,我们就会使pattern向右移动的位置变大,而较少的移动位置是存在匹配的,这样我们就会把可能匹配的结果丢失。比如下面的序列,

在红色部分失配,正确的结果是k=1的情况,把pattern右移4位,如果选择k=0,右移5位则会产生错误。计算这个overlay函数的方法可以采用递推,可以想象如果对于pattern的前j个字符,如果覆盖函数值为k

a0a1…ak-1ak=aj-kaj-k+1…aj-1aj
则对于pattern的前j+1序列字符,则有如下可能
⑴     pattern[k+1]==pattern[j+1] 此时overlay(j+1)=k+1=overlay(j)+1
⑵     pattern[k+1]≠pattern[j+1] 此时只能在pattern前k+1个子符组所的子串中找到相应的overlay函数,h=overlay(k),如果此时pattern[h+1]==pattern[j+1],则overlay(j+1)=h+1否则重复(2)过程.

下面给出一段计算覆盖函数的代码:

  1. //copyright@ staurman
  2. //updated@2011 July
  3. #include ”StdAfx.h”
  4. #include<iostream>
  5. #include<string>
  6. using namespace std;
  7. //solve to the next array
  8. void compute_overlay(const string& pattern)
  9. {
  10.     const int pattern_length = pattern.size();
  11.     int *overlay_function = new int[pattern_length];
  12.     int index;
  13.     overlay_function[0] = -1;
  14.     for(int i=1;i<pattern_length;++i)
  15.         //注,与上文代码段一不同的是,此处i是从1开始的,所以,下文中运用俩种方法求出来的next数组各值会有所不同
  16.     {
  17.         index = overlay_function[i-1];
  18.         //store previous fail position k to index;
  19.         while(index>=0 && pattern[i]!=pattern[index+1])
  20.         {
  21.             index = overlay_function[index];
  22.         }
  23.         if(pattern[i]==pattern[index+1])
  24.         {
  25.             overlay_function[i] = index + 1;
  26.         }
  27.         else
  28.         {
  29.             overlay_function[i] = -1;
  30.         }
  31.     }
  32.     for(int i=0;i<pattern_length;++i)
  33.     {
  34.         cout<<overlay_function[i]<<endl;
  35.     }
  36.     delete[] overlay_function;
  37. }
  38. //abaabcaba
  39. int main()
  40. {
  41.     string pattern = ”abaabcaba”;
  42.     compute_overlay(pattern);
  43.     system(“pause”);
  44.     return 0;
  45. }

    运行结果如下所示:

 

2.2、kmp算法
     有了覆盖函数,那么实现kmp算法就是很简单的了,我们的原则还是从左向右匹配,但是当失配发生时,我们不用把target_index向回移动,target_index前面已经匹配过的部分在pattern自身就能体现出来,只要动pattern_index就可以了。

当发生在j长度失配时,只要把pattern向右移动j-overlay(j)长度就可以了。

如果失配时pattern_index==0,相当于pattern第一个字符就不匹配,这时就应该把target_index加1,向右移动1位就可以了。

ok,下图就是KMP算法的过程(红色即是采用KMP算法的执行过程):

(另一作者saturnman发现,在上述KMP匹配过程图中,index=8和index=11处画错了。还有,anaven也早已发现,index=3处也画错了。非常感谢。但图已无法修改,见谅)

KMP 算法可在O(n+m)时间内完成全部的串的模式匹配工作。

OK,下面此前写的关于KMP算法的第一篇文章中的源码:

  1. //copyright@ saturnman
  2. //updated@ 2011 July
  3. #include ”stdafx.h”
  4. #include<iostream>
  5. #include<string>
  6. #include <vector>
  7. using namespace std;
  8. int kmp_find(const string& target,const string& pattern)
  9. {
  10.     const int target_length=target.size();
  11.     const int pattern_length=pattern.size();
  12.     int* overlay_value=new int[pattern_length];
  13.     overlay_value[0]=-1;        //remember:next array’s first number was -1.
  14.     int index=0;
  15.     //next array
  16.     for (int i=1;i<pattern_length;++i)
  17.         //注,此处的i是从1开始的
  18.     {
  19.         index=overlay_value[i-1];
  20.         while (index>=0 && pattern[index+1]!=pattern[i])  //remember:!=
  21.         {
  22.             index=overlay_value[index];
  23.         }
  24.         if(pattern[index+1] == pattern[i])
  25.         {
  26.             overlay_value[i]=index+1;
  27.         }
  28.         else
  29.         {
  30.             overlay_value[i]=-1;
  31.         }
  32.     }
  33.     //mach algorithm start
  34.     int pattern_index=0;
  35.     int target_index=0;
  36.     while (pattern_index<pattern_length && target_index<target_length)
  37.     {
  38.         if (target[target_index] == pattern[pattern_index])
  39.         {
  40.             ++target_index;
  41.             ++pattern_index;
  42.         }
  43.         else if(pattern_index==0)
  44.         {
  45.             ++target_index;
  46.         }
  47.         else
  48.         {
  49.             pattern_index=overlay_value[pattern_index-1]+1;
  50.         }
  51.     }
  52.     if (pattern_index==pattern_length)
  53.     {
  54.         return target_index-pattern_index;
  55.     }
  56.     else
  57.     {
  58.         return -1;
  59.     }
  60.     delete [] overlay_value;
  61. }
  62. int main()
  63. {
  64.     string sourc=”ababc”;
  65.     string pattern=”abc”;
  66.     cout<<kmp_find(sourc,pattern)<<endl;
  67.     system(“pause”);
  68.     return 0;
  69. }

由于是abc跟ababc匹配,那么将返回匹配的位置“2”,运行结果如所示:

 

第四部分、测试

针对上文中第三部分的两段代码测试了下,纠结了,两种求next数组的方法对同一个字符串求next数组各值,得到的结果竟然不一样,如下二图所示:

1、两种方法对字符串abab求next数组各值比较:

2、两种对字符串abaabcaba求next数组各值比较:

为何会这样呢,其实很简单,上文中已经有所说明了,代码实现一的i 是从0开始的,代码实现二的i 是从1开始的。但从最终的运行结果来看,暂时还是以代码实现段二为准。

第五部分、KMP完整准确源码

求next数组各值的方法为:

  1. //copyright@ staurman
  2. //updated@2011 July
  3. #include ”StdAfx.h”
  4. #include<iostream>
  5. #include<string>
  6. using namespace std;
  7. //solve to the next array
  8. void compute_overlay(const string& pattern)
  9. {
  10.     const int pattern_length = pattern.size();
  11.     int *overlay_function = new int[pattern_length];
  12.     int index;
  13.     overlay_function[0] = -1;
  14.     for(int i=1;i<pattern_length;++i)
  15.     {
  16.         index = overlay_function[i-1];
  17.         //store previous fail position k to index;
  18.         while(index>=0 && pattern[i]!=pattern[index+1])
  19.         {
  20.             index = overlay_function[index];
  21.         }
  22.         if(pattern[i]==pattern[index+1])
  23.         {
  24.             overlay_function[i] = index + 1;
  25.         }
  26.         else
  27.         {
  28.             overlay_function[i] = -1;
  29.         }
  30.     }
  31.     for(int i=0;i<pattern_length;++i)
  32.     {
  33.         cout<<overlay_function[i]<<endl;
  34.     }
  35.     delete[] overlay_function;
  36. }
  37. //abaabcaba
  38. int main()
  39. {
  40.     string pattern = ”abaabcaba”;
  41.     compute_overlay(pattern);
  42.     system(“pause”);
  43.     return 0;
  44. }

运行结果入下图所示:abab的next数组各值是-1,-1,0,1,而非本文第二部分所述的-1,0,-1,0。为什么呢?难道是搬石头砸了自己的脚?

NO,上文第四部分末已经详细说明,上处代码i 从0开始,本文第二部分代码i 从1开始。

 

KMP算法完整源码,如下:

  1. //copyright@ saturnman
  2. //updated@ 2011 July
  3. #include ”stdafx.h”
  4. #include<iostream>
  5. #include<string>
  6. #include <vector>
  7. using namespace std;
  8. int kmp_find(const string& target,const string& pattern)
  9. {
  10.     const int target_length=target.size();
  11.     const int pattern_length=pattern.size();
  12.     int* overlay_value=new int[pattern_length];
  13.     overlay_value[0]=-1;        //remember:next array’s first number was -1.
  14.     int index=0;
  15.     //next array
  16.     for (int i=1;i<pattern_length;++i)
  17.         //注,此处的i是从1开始的
  18.     {
  19.         index=overlay_value[i-1];
  20.         while (index>=0 && pattern[index+1]!=pattern[i])
  21.         {
  22.             index=overlay_value[index];
  23.         }
  24.         if(pattern[index+1] == pattern[i])
  25.         {
  26.             overlay_value[i]=index+1;
  27.         }
  28.         else
  29.         {
  30.             overlay_value[i]=-1;
  31.         }
  32.     }
  33.     //mach algorithm start
  34.     int pattern_index=0;
  35.     int target_index=0;
  36.     while (pattern_index<pattern_length && target_index<target_length)
  37.     {
  38.         if (target[target_index] == pattern[pattern_index])
  39.         {
  40.             ++target_index;
  41.             ++pattern_index;
  42.         }
  43.         else if(pattern_index==0)
  44.         {
  45.             ++target_index;
  46.         }
  47.         else
  48.         {
  49.             pattern_index=overlay_value[pattern_index-1]+1;
  50.         }
  51.     }
  52.     if (pattern_index==pattern_length)
  53.     {
  54.         return target_index-pattern_index;
  55.     }
  56.     else
  57.     {
  58.         return -1;
  59.     }
  60.     delete [] overlay_value;
  61. }
  62. int main()
  63. {
  64.     string sourc=”ababc”;
  65.     string pattern=”abc”;
  66.     cout<<kmp_find(sourc,pattern)<<endl;
  67.     system(“pause”);
  68.     return 0;
  69. }

    运行结果如下:

 

第六部分、一眼看出字符串的next数组各值

上文已经用程序求出了一个字符串的next数组各值,接下来,稍稍演示下,如何一眼大致判断出next数组各值,以及初步判断某个程序求出的next数组各值是不是正确的。有一点务必注意:下文中的代码全部采取代码实现二,即i是从1开始的。

  • 1、对字符串aba求next数组各值,各位可以先猜猜,-1,…,aba中,a初始化为-1,第二个字符b与a不同也为-1,最后一个字符和第一个字符都是a,所以,我猜其next数组各值应该是-1,-1,0,结果也不出所料,如下图所示:

 

  • 2、字符串“abab”呢,不用猜了,我已经看出来了,当然上文中代码实现一和代码实现二都已经求出来了。如果i 是1开始的话,那么next数组各值将如代码实现二所运行的那样,将是:-1,-1,0,1;
  • 3、字符串“abaabcaba”呢,next数组如上第三部分代码实现二所述,为-1,-1,0,0,1,-1,0,1,2;
  • 4、字符串“abcdab”呢,next数组各值将是-1,-1,-1,-1,0,1;
  • 5、字符串“abcdabc”呢,next数组各值将是-1,-1,-1,-1,0,1,2;
  • 6、字符串“abcdabcd”呢,那么next数组各值将是-1,-1,-1,-1,0,1,2,3;

 

怎么样,看出规律来了没?呵呵,可以用上述第五部分中求next数组的方法自个多试探几次,相信,很快,你也会跟我一样,不用计算,一眼便能看出某个字符串的next数组各值了。如此便恭喜你,理解了next数组的求法,KMP算法也就算是真真正正彻彻底底的理解了。完。

相关链接

  1. KMP之第二篇文章:六(续)、从KMP算法一步一步谈到BM算法
  2. KMP之第一篇文章:六、教你初步了解KMP算法、updated

后记

     相信,看过此文后,无论是谁,都一定可以把KMP算法搞懂了(但万一还是有读者没有搞懂,那怎么办呢?还有最后一个办法:把本文打印下来,再仔细琢磨。如果是真真正正想彻底弄懂某一个东西,那么必须付出些代价。但万一要是打印下来了却还是没有弄懂呢?那来北京找我吧,我手把手教你。祝好运)。
    在结束全文之前,谈两点感悟:
  1. 语言->数据结构->算法:语言是基础,够啃一辈子,基本的常见的数据结构得了如指掌,最后才是算法。除了算法之外,有更多更重要且更值得学习的东西(最重要的是,学习如何编程)。切勿盲目跟风,找准自己的兴趣点,和领域才是关键。这跟选择职位、与领域并持久做下去,比选择公司更重要一样。选择学什么东西不重要,重要的是你的兴趣。
  2. 修订这篇文章之时,个人接触KMP都有一年了,学算法也刚好快一年。想想阿,我弄一个KMP,弄了近一年了,到今天才算是真正彻底理解其思想,可想而知,当初创造这个算法的k、m、p三人是何等不易。我想,有不少读者是因为我的出现而想学算法的,但不可急功近利,切勿妄想算法速成。早已说过,学算法先修心。
     OK,文中有关任何问题或错误,烦请不吝赐教与指正。谢谢,完。
    作者:July。
    July、二零一一年十二月五日中午。

出处:http://blog.csdn.net/v_JULY_v/

WordPress数据库查询SELECT YEAR(post_date) AS `year`, MONTH(post_date) AS `month`, count(ID) as posts FROM wp_posts WHERE post_type = 'post' AND post_status = 'publish' GROUP BY YEAR(post_date), MONTH(post_date) ORDER BY post_date DESC 时发生Expression #1 of ORDER BY clause is not in GROUP BY clause and contains nonaggregated column 'jingjing.wp_posts.post_date' which is not functionally dependent on columns in GROUP BY clause; this is incompatible with sql_mode=only_full_group_by错误,这是由require('wp-blog-header.php'), require_once('wp-includes/template-loader.php'), include('/themes/green-hope/archive.php'), get_sidebar, locate_template, load_template, require_once('/themes/green-hope/sidebar.php'), dynamic_sidebar, call_user_func_array, WP_Widget->display_callback, WP_Widget_Archives->widget, wp_get_archives查询的。

Copyright © All Rights Reserved · 菁菁博客 Since 2012 · Proudly powered by WordPress