数据结构基础—串
一、串类型定义
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]值
- 若发现不同，则next[j] = 上一个next的值
- 若最后匹配到next = 0 则，next[j] = 0
-
若不同，则next[j]的值不变