数据结构基础—串

一、串类型定义

1.串的定义和相关概念

字符串一般简称为串，其实就是由零个或多个字符组成的有限序列。逻辑结构和线性表极为相似，只是串的数据类型为字符型。

零个字符放入串称为空串

串中任意连续字符组成的子序列称为该串的子串

包含子串的串为主串

二、串的表示与实现

1.串的表示

串的表示分为三种分别是：定长顺序，堆分配，块链存储

各个表示的注意事项:

• 定长顺序：S[0]的值为串的长度
• 堆分配：动态链式的存储，是从0开始的
• 每个节点就是一个串

2.串的基本操作(实现)

对串的操作，通常是”串为整体“操作，最基本的有六个操作

请见下方的代码:

//求串长          
int Strstrlen(char a[]){
	int i = 1;
	for(;a[i] !='\0';){
		i++;
	}
	return i;
} 

//复制S->T 
void StrCopy(char(&T)[MaxSize+1],char S[]){
	int i = 1;
	T[0] = S[0];
	while(i <= S[0]){
		T[i] = S[i];
		i++;
	}
} 

//赋值 
void StrAssige(char(&S)[MaxSize+1],char a[]){
	if(Strstrlen(a) > MaxSize){
		cout << "赋值失败";
		return;
	}
	S[0] = Strstrlen(a);
	for(int i = 1;i <= Strstrlen(a);i++){
		S[i] = a[i-1];
	}
	cout << "赋值成功\n";
}

//比较
int StrCompare(char s[],char T[]){//ok 
	int i;
	for(i = 1;i <= T[0];i++){
		if(s[i] != T[i]) return 1;
		if(s[i] == '#') return 1;
	}
	return 0;
} 

//求子串
void Substring(char S[],char(&s)[MaxSize+1],int pos,int len){
	int i;
	if(pos < 1|| pos > S[0] || len > S[0] - pos +1){//不和法，不求子串但还是给赋个值 
		s[i] = '#';
		return ;
	}
	for(int i = 1;i <= len;i++){
		s[i] = S[pos + i -1];
	}
} 

//联接
void Concat(char(&New)[MaxSize+1],char V[]){
	if(New[0]+V[0] > MaxSize){
		cout << "发生截断\n";//这里写的比较简单 
		return ; 
	}
	int j = New[0];
	for(int i = 1;i <= V[0];i++){//小于要接入的串长 
		New[j+i] = V[i];
	}
	New[0] = New[0] + V[0];
} 

三、串的模式匹配算法

问题描述

有两个串T（模式串）,S（主串），T在S中第一次匹配的位置是哪里

1、简单算法(暴力枚举)

两串逐一比较

• 相同：i++;j++;
• 失配：i 和 j 的位置更替。i：回溯再+1(i = i - j +2)；j =1;

匹配成功：j > n(n:子串的长度(T[0]))

2、首尾匹配

先比较子串的首位，最后比较第二个到n-1个...

3、KMP算法

时间复杂度：O(m*n)->O(m+n)

若当前位置不匹配，且不匹配的位置不为1，但是在子串的当前位置的前面前面有与开头相同的元素，则下次时，不需要比较这些相同的元素,即：

• 主串i位置不变(不需要回溯)
• 子串向右滑动>=1位(不一定回到第一个位置)

---

eg:T串为 a b c a c 时，在 c 的位置不匹配，则下次从 b 开始比较(即：j = 2)

---

j 如何移动(j的下一个位置)？

只与模式串有关，使用 next[j] 数组来存放下一个位置

next的值的含义：

• next = 0，第一个元素
• next = 1，无相同的子串
• next = k ,在第 k 个位置前所有的子串与 k 后到 j(next值) 前所有子串相同（这个很重要，k相当于相同子串的分隔）

要计算当前next[j]的值则要根据前一位元素的next值来确定(需要一个计数的i(前一个位置)和判断的 j = next[i] (next[i]位置，相同子串的分隔))

j == 0说明无相同子串(第0个位置，啥也没有)，直接将当前的next赋值为1，并更新j,因让 j == 1，以便于接下来的比较(如果第一个位置与模式串中第i位置相同，则说明有一个相同子串next值就等于2了，依次类推)

---

此图为多次分割，颜色相同或是数字相同的元素代表了他们相同，便于理解

---

计算当前位置的next

由上述的说明可知要想求得当前位置的next只需比较第i个位置和第j(next[i])个位置的值是否相同,

• 若相同，则next = 前一位置的next+1,(前串已根据next[i判断好])同时更新 i 和 j 的值（next[++i] = ++j）

• 若不相同，则让 j = next[j] 的值（再分割），再与第i个元素比较，直到相同或是 j == 0;

遍历结束，即完成

代码如下：

//普通KMP算法
void GetNext(char T[],int len,int next[]){
    next[1] = 0;
    int i = 1;
    j = 0;
    while(i <= len){
        if( j == 0 || T[j] == T[i]){
            next[++i] = ++j;
        }
        else{ j = next[j]; }
   }
    
}

完整代码：

#include<iostream>
#include<cstdlib> 
#define MaxSize 30 
using namespace std;

//求串长        
int Strstrlen(char a[]){
	int i = 1;
	for(;a[i] !='\0';){
		i++;
	}
	return i;
} 

//赋值函数 
void StrAssige(char(&S)[MaxSize+1],char a[]){
	if(Strstrlen(a) > MaxSize){
		cout << "赋值失败";
		return;
	}
	S[0] = Strstrlen(a);
	for(int i = 1;i <= Strstrlen(a);i++){
		S[i] = a[i-1];
	}
	cout << "赋值成功\n";
}

//获取next的值 
void GetNext(char T[],int len,int next[]){
    next[1] = 0;
    int i = 1;
    int j = 0;
    while(i <= len){
        if( j == 0 || T[j] == T[i]){//第一个位置或是有相等 
            next[++i] = ++j;
        }
        else{ j = next[j]; } //分割处 
   }  
}

int KMP(char *S,char *T){
	int next[MaxSize+1];
	GetNext(T,T[0],next);
	cout << "next 的值为："; 
	for(int m = 1;m <= T[0];m++){
		cout << next[m];
	}
	cout << endl;//next正常 
	int i = 1;
	int j = 1;
	while(i <= S[0] && j <= T[0]){
		if(j == 0 ||  S[i] == T[j]){//不匹配位置 = 1或是匹配 
			i++;
			j++;
		} else{
			j = next[j];
		}
	}	
	if(j > T[0]) return i-T[0];
	return 0;
}

int main(){
	char a[MaxSize+1];
	//原串
	char S[MaxSize+1];
	cout << "请输入原串(S)的串："; 
	gets(a);
	StrAssige(S,a);
	
	//模式串
	char T[MaxSize+1];
	cout << "请输入模式串：";
	gets(a);
	StrAssige(T,a);
	
	//匹配 
	int j;
	j = KMP(S,T);
	cout << j;
	return 0;
}

next[j]取值的改进(了解)

将当前元素的next[j]值与模式串中 j 位置的值比较，

• 若相同，则还要与 j 位置next值位置的元素比较，直到next = 0或是不同.当前位置的next[j] = j 位置的next[j]值

  1. 若发现不同，则next[j] = 上一个next的值
  2. 若最后匹配到next = 0 则，next[j] = 0

• 若不同，则next[j]的值不变