栈，队列，串

  栈是一种特殊的队列，串指字符串

一、栈

定义

   栈：线性表，只允许在一段进行插入或删除操作。
    重要术语：栈顶，栈底，空栈
   后进先出(LIFO)

基本操作

   初始化

InitStack(&S);

   销毁

DestoryStack(&S);

   进栈

Push(&S,x);

   出栈

Pop(&S,&x);

   读取栈顶元素

GetTop(S,&x);

二、队列

定义

   队列：只允许在一端进行插入，在另一端进行删除的线性表
     重要术语：队头，队尾，空队列
   先进先出(FIFO)

基本操作

   初始化

InitQueue(&Q);

   销毁

DestoryQueue(&Q);

   入队

Enqueue(&Q,x)

   出队

Dequeue(&Q,&x);

   获取队头元素

GetHead(Q,&x);

    双端队列：允许从两端进行插入和删除

三、串

定义

    字符串
     字符位置下标从一开始

串的朴素模式匹配算法

int Index(SString S,SString T){
	int k=1;//指向主串
	int i=k,j=1; //i指向字串，j指向待匹配串
	while(i<=S.length&&j>=T.length){
		if(s.ch[i]==T.ch[j]){
			++i;
			++j;
		}else{
			k++;
			i=k;
			j=1;
		}
	}
	if(j>T.length)
		return k;
	else
		return 0;
}

   时间复杂度最坏情况O(nm)
   例如：
    主串：aaaaaaaab
    字串：aaab

KMP算法

求next数组

   当第j个字符不匹配，由前1-j-个字符组成的串记为S，则：next[j]=S的最长相等前后缀长度+1；
   特别的next[1]=0

$$Max\left(k|1<k<j且p_i···p_{k-1}=p_{j-k+1}···p_{j-1}\right)$$

   其他情况，前后缀不匹配，设为1.

void get_next(SString T,int next[]){
	int i=1,j=0;
	next[1]=0;
	while(i<T.length){
		if(j==0||T.ch[i]==T.ch[j]){
			++i;
			++j;
			//若pi=pj，则next[j+1]=next[j]+1
			next[i]=j;
		}else{
		//否则令j=next[j],循环继续
			j=next[j];
		}
	}
}

kmp算法

int Index_KMP(SString S,SString T){
	int i=1,j=1;
	int next[T.length+1];
	get_next(T,next);
	while(i<=S.length&&j<=T.length){
		if(j==0||S.ch[i]==T.ch[j]){
			++i;++j;//继续比较后继字符
		}else{
			j=next[j];//匹配串回溯。向右
		}
	}
	if(j>T.length)
		return i-T.length;
	else return 0;
}

优化后的KMP算法

   nextval数组

void getNextVal(SString T,int next[],int size){
	int nextval[size];
	nextvla[1]=0;
	for(int j=0;j<=T.length){
		if(T.ch[next[j]]==T.ch[j])
			nextval[j]=nextval[next[j]];
		else
			nextval[j]=next[j];
	}
}
int Index_KMP(SString S,SString T){
	int i=1,j=1;
	int next[T.length+1];
	get_next(T,next);
	while(i<=S.length&&j<=T.length){
		if(j==0||S.ch[i]==T.ch[j]){
			++i;++j;//继续比较后继字符
		}else{
			j=nextval[j];//匹配串回溯。向右
		}
	}
	if(j>T.length)
		return i-T.length;
	else return 0;
}

打赏