串：
空串 “”
空格串 " "
子串 包含自身
真子串 不包含自身

子串：n(n+1)/2+1
真子串：n(n+1)/2
非空真子串：n(n+1)/2-1
非空子串：n(n+1)/2

字符串匹配 strcpy_s
字符串匹配 BF算法（朴素算法） KMP算法
字符串比较 strcmp strncmp
字符串长度 strlen
字符串链接 strcat

---

字符串匹配

主串 子串 在主串中寻找和子串相同的子串，有相等的则返回最开始的下标，没有相等的则返回-1

BF算法（朴素算法）

算法思想：

首先有两个字符串，str是主串，sub是子串，pos是从主串中的第几个位置开始比较；i保存主串中的下标，j保存子串中的下标；
str[i] == sub[j] 则j++,i++
不相等，则i=i-j+1;(i要返回到失配前位置的下一个);j=0;
主串中一个一个字符进行比较

代码实现

int BF_search(const char* str, const char* sub, int pos)
{
	if (str == nullptr || sub == nullptr || pos < 0 || pos >= strlen(str))
	{
		return -1;
	}
	int lenstr = strlen(str);
	int lensub = strlen(sub);
	int i = pos; //存放主串匹配时的下标
	int j = 0;   //存放子串匹配时的下标

	while (i < lenstr && j < lensub)
	{
		if (str[i] == sub[j])
		{
			i++;
			j++;
		}
		else
		{
			i = i - j + 1; //i要返回到失配前位置的下一个
			j = 0;
		}
	}
	if (j >= lensub)       //j走到最后 找到有匹配的子串
	{
		return i - j;      //返回匹配前位置
	}
	return -1;              //没有走到尾  找不到对应子串
}

int main()
{
	const char* a = "acdfshfcdf";
	const char* b = "cdf";
	int n = BF_search(a, b, 4);
	//从主串第4 个元素后查找是否有对应的子串
	cout << "匹配的位置是：" << n << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

KMP算法

特点：主串中的i不回退
为什么i不回退？ j回退到哪？

• 失配的两种情况：

1. 发生失配情况时，子串前面的字符串互不相等
   

   字符串互不相等，完全没有必要让i回退，i回退了，也会失配

2. 发生失配情况时，字符串前面有字符相等
   

   i如果回退，虽然有价值，但是接下来走得几步都是一定成功，为了避免让i回退，选择让j回退到合适的位置，而不是回退到0；（这个位置记作k）

• 如何求得合适的位置K，
  K->当前面有字符相等，在发生失配时j应该会退到的位置
  每一个位置都有失配的可能性，所以每个位置都要有一个合适的回退位置K
  
  （1）发生失配时向前看，看是否有两个相等的最长真子串，一个顶着头部，一个尾巴顶着失配前的位置，则真子串的长度就为K
  我们规定next[0] = -1;next[1] = 0;

举例（求next数组）：

a bcdef	a bcabc	a bcdabc	a bcabcabcdabdef
-100000	-100012	-1000012	-100012345601200

（2）判断哪一个位置的K值时，可以观察前一个字符与其相对应的K位置上的字符比较看是否相等，如果相等则将K++赋值给该位置的K，如果不相等则赋值为0

int* Get_next(const char* sub)   //next数组只与子串有关
{
	assert(sub != NULL);
	int len = strlen(sub);     //子串长度 用来开辟一个同等长度的next数组
	int* next = (int*)malloc(sizeof(int) * len);//申请等长的数组空间保存回退的下标
	assert(next != NULL);
	next[0] = -1;   //固定的值
	next[1] = 0;    //固定的值
	int j = 1;   //1号坐标开始
	int k = 0;
	//通过已知推未知
	while (j + 1 < len)     //给next数组的每一个位置都找到合适的值
	{
		if ((k == -1) || sub[j] == sub[k])
		{               //相等的话将该位置的k加一赋给下一个位置的k
			k++;
			j++;
			next[j] = k;
		}
		else
		{
			k = next[k];//k回退到合适的位置
		}
	}
	return next;   //返回出next数组
}
int KMP_Search(const char* str, const char* sub, int pos)
{
	assert(str != nullptr && sub != nullptr);
	if (str == nullptr || sub == nullptr || pos < 0 || pos >= strlen(str))
	{
		return -1;
	}
	int lenstr = strlen(str);   ///主串的长度
	int lensub = strlen(sub);   //子串的长度
	int i = pos;   //保存主串匹配时的下标
	int j = 0;     //保存子串匹配时的下标
	int* next = Get_next(sub);
	while (i < lenstr && j < lensub)
	{
		if ((j == -1) || str[i] == sub[j])
		{       //相等 i++ j++
			i++;
			j++;
		}
		else
		{
			j = next[j];   //j回退到合适的位置
		}
	}
	//需要判断是哪种情况是while退出循环
	if (j >= lensub)
	{   //j走到最后
		return i - j;//回到匹配前的位置
	}
	//j没有走到尾  没有子串一样的字符串  返回-1
	return -1;

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60