【数据结构】串

【数据结构】串

本当迷

2021 年 09 月 29 日

1019 次浏览

暂无评论

362字数

数据结构

## 串：

### 串的定义：

串是由零个或多个字符组成的有限序列，又叫字符串

### 串的抽象数据类型

```cpp
ADT 串(string)
Date
串中元素仅由一个字符组成，相邻元素具有前驱和后继
Operation
	StrAssign(T, *chars);//生成一个其值等于字符串常量chars的串T
	StrCop(T, S);//串S存在，由串S复制得串T
	ClearString(S);//若串存在，将串清空
	StringEmpty(S);//若串为空返回ture,否则返回false
	StrLength(S);//返回串S的元素个素，即串的长度
	StrCompare(S,T);//若S > T,返回>0;若S = T,返回0;若S < T,返回<0
	Concat(T1, S1, S2);//用T返回由S1和S2联结而成新串
	SubString(Sub,S,pos,len);//用Sub返回串S的第pos个字符起长度为len的字串
	Index(S,T,pos);//若主串S中存在和串T值相同的字串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0
	Replace(S,T,V);//用V替换主串S中出现的所以与T相等的不重叠的字串
	StrInsert(S,pos,T);//在串S的第pos个字符之前插入串T
	StrDelete(S,pos,len);//从串中删除第pos个字符起长度为len的字串
endADT
```

## 朴素的模式匹配算法

```cpp
#include<stdio.h>
#include<string>
using namespace std;

int Index(string S, string T, int pos)
{
	int i = pos;//用于S主串下标，从pos位置开始匹配
	int j = 0;//用于T字串下标

while (i < S.size() && j < T.size())//当i小于S的长度并且j小于T的长度，循环继续
	{
		if (S[i] == T[j])//两字母相等则继续
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1;//i退回到上一次匹配首位的下一位
			j = 0;//j退回到字串T的首位
		}
	}
	if (j == T.size())//当j等于T的长度，说明字符匹配成功
	{
		return i - T.size();
	}
	else
	{
		return -1;
	}
}

int main()
{
	string S = "abcdefghijkl";
	string T = "ghijk";
	int index = Index(S, T, 0);

printf("匹配下标为：%d", index);
	return 0;
}
```

## KMP模式匹配算法

```cpp
#include<stdio.h>
#include<string>
#include<vector>
using namespace std;

void get_next(string T, vector<int> &next)
{
	int j = 0, k = -1;
	next[0] = -1;//next[0] 必为-1

while (j < T.size() - 1)
	{
		if (k == -1 || T[j] == T[k])
		{
			j++;
			k++;
			next[j] = k;
		}
		else//不相等，k回溯到与最大后缀 相等的最大前缀的下一个下标，若k一直回溯下去都不相等，则回溯至-1为止
		{
			k = next[k];
		}
	}
}

int Index(string S, string T)
{
	int i = 0;//用于S主串下标，从pos位置开始匹配
	int j = 0;//用于T字串下标

vector<int>next;
	next.resize(T.size());
	get_next(T, next);
	int S_len = S.size();
	int T_len = T.size();

while (i < S_len && j < T_len)//当i小于S的长度并且j小于T的长度，循环继续
	{
		if (j == -1 || S[i] == T[j])//两字母相等则继续
		{
			i++;
			j++;
		}
		else
		{
			j = next[j];
		}
	}
	if (j == T_len )//当j等于T的长度，说明字符匹配成功
	{
		return i - j;
	}
	else
	{
		return -1;
	}
}

int main()
{
	string S = "abcdefghijkl";
	string T = "hijk";
	int index = Index(S, T);

printf("匹配下标为：%d", index);
	return 0;
}
```

最后修改：2021 年 10 月 02 日