字符串
一、定义
1.C语言中
C语言中以结束字符\0结尾的字符数组表示字符串
字符串通常是通过字符数组或者字符指针来表示的。定义字符串的常见方式有：
1
2
3
4
5
|
char str1[] = "Hello, World!";
char *str2 = "Hello, World!";
|
相关操作：
C语言标准库提供了一些处理字符串的函数，这些函数都在 <string.h> 头文件中定义
**strlen**：计算字符串的长度，不包括 '\0'
**strcpy**：将一个字符串复制到另一个字符串中
1
2
| char dest[20];
strcpy(dest, str1);
|
**strcat**：将两个字符串连接在一起
**strcmp**：比较两个字符串的大小（按字典顺序）
1
2
3
| if (strcmp(str1, str2) == 0) {
}
|
二、字符串的实现
1.String.h
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
| #pragma once
#include <iostream>
#include <vector>
class String{
private:
char *s;
int _size;
public:
String(const char *str);
String(const String &string);
~String();
int size() const;
char operator[](int i) const;
char &operator[](int i);
String subString(int pos, int n);
String& operator+=(const String &str);
int find(String T, int pos = 0);
int find_KMP(String T, int pos=0);
void get_next(std::vector<int> &next);
friend std::ostream &operator<<(std::ostream &ostream, const String &str);
};
|
2.string.cpp
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
| #include "String.h"
#include "exception"
String::String(const char *str):s(nullptr),_size(0)
{
if(str == nullptr)
return;
int n = 0;
while(str[n] != '\0')
{
n++;
}
s = new char[n+1];
if(s == nullptr)
throw "内存分配失败";
for(int j = 0;j<n;j++)
{
s[j] = str[j];
}
_size = n;
}
String::String(const String &string)
{
this->_size = string.size();
this->s = new char[this->_size + 1];
for(int j = 0;j<_size;j++)
{
s[j] = string[j];
}
}
String::~String()
{
if(this->s != nullptr)
{
_size = 0;
delete s;
}
}
int String::size() const
{
return _size;
}
char String::operator[](int i) const
{
if(i<0 || i>=_size)
throw "索引越界";
return s[i];
}
char & String::operator[](int i)
{
if(i<0 || i>=_size)
throw "索引越界";
return s[i];
}
String String::subString(int pos, int n)
{
if(pos < 0 || pos >= _size)
{
throw "位置非法";
}
if(pos+n > _size)
{
throw "超出";
}
char *p = new char[n+1];
if(p == nullptr)
throw "内存分配失败";
for(int j=0,i=pos; j<n; j++,i++)
{
p[j] = s[i];
}
p[n] = '\0';
String str(p);
delete[] p;
return str;
}
String & String::operator+=(const String &str)
{
int newSize = this->_size + str.size();
char *p = new char [newSize + 1];
if(p == nullptr)
return *this;
int j=0;
while(j<_size)
{
p[j] = this->s[j];
j++;
}
int i = 0;
while(i<str.size())
{
p[j] = str[i];
i++;
j++;
}
delete this->s;
s = p;
_size = newSize;
}
std::ostream& operator<<(std::ostream &ostream, const String &str)
{
return (ostream << str.s);
}
|
三、匹配算法
1.朴素匹配算法
假设主串为S=goodgoogle，从起始位置pos=0，开始进行搜索子串T=google的位置
主串S第一位开始，S与T前三个字母都匹配成功，但S第四个字母是d而T的是 g。第一位匹配失败
主串S第二位开始，主串S首字母是o，要匹配的T首字母是g，匹配失败
主串S第三位开始，主串S首字母是o，要匹配的T首字母是 g，匹配失败
主串S第四位开始，主串S首字母是d，要匹配的T首字母是g，匹配失败
主串S第五位开始，S与T，6个字母全匹配，匹配成功
总结：
- 简单的说，就是对主串的每一个字符作为子串开头，与要匹配的字符串进行匹配。对主串做大循环，每个字符开头做
T的长度的小循环，直到匹配成功或全部遍历完成为止
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
|
int String::find(String T, int pos)
{
int i = pos;
int j = 0;
while(i<this->_size && j<T.size())
{
if(s[i] == T[j])
{
j++;
}
else{
i = i-j;
j=0;
}
i++;
}
if(j >= T.size())
return i-j;
else
return -1;
}
|
2.KMP模式匹配算法
在朴素匹配算法中，当遇到字符不匹配时，模式串需要向右移动一位（下一次从此次主串匹配的首位的下一位开始匹配），然后重新从头开始比较。KMP算法的关键优化点在于：当遇到不匹配时，利用已经匹配的部分信息，避免将模式串完全向右移动，减少不必要的重复匹配
- 在朴素匹配算法中，记录主串中索引位置
i需要进行回溯，当遇到不匹配的字符时候，需要减去已经与模式串进行匹配的长度j
KMP算法就是可以让主串中的i少发生一些没必要的回溯
KMP的算法步骤：
模式串的next数组：
- 记录模式串字符串索引位置
j，不含当前位置字符前面的字符串的前缀与缀的最大匹配长度（不含有整体）
进行字符串的匹配：
- 利用
next数组，加速匹配的过程，当匹配过程中出现不匹配时，模式串不需要回退到起始位置，而是根据部分next数组决定模式串向右移动的位数，从而避免重复匹配
时间复杂度：
KMP算法的时间复杂度是 O(n + m)，其中 n 是文本串的长度，m 是模式串的长度。相比于暴力算法的 O(n * m) 的复杂度，KMP算法在大多数情况下有着显著的性能提升
（1）next数组
对于任意字符串，索引j=0与j=1的next数组的值均为
如下，对于模式串aabbaabsaabaaax的next数组：
（2）使用模式串的next数组加速匹配过程
若，主串为：S1 = aabaabcaabaabaabcaabaabt
模式串S2 = aabaabcaabaabt
模式串S2的next数组为[-1 0 1 0 1 2 3 0 1 2 3 4 5 6]
匹配过程：
完整过程：可以匹配成功
（3）模式串next数组求解
不用根据之前求得的next索引位置的值进行跳跃
跳跃一次
代码实现
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
|
void String::get_next(std::vector<int> &next)
{
next[0] = -1;
next[1] = 0;
int i = 2, cn = 0;
while(i < next.size())
{
if(s[i-1] == s[cn])
{
next[i] = ++cn;
i++;
}
else if(cn > 0)
{
cn = next[cn];
}
else
{
next[i] = 0;
i++;
}
}
}
|
（4）KMP匹配主流程
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
|
int String::find_KMP(String T, int pos)
{
int x = 0;
int y = 0;
int n = this->size();
int m = T.size();
std::vector<int> next(m);
get_next(next);
while (x < n && y < m)
{
if(this->s[x] == T[y])
{
x++;
y++;
}
else if(y==0)
{
x++;
}
else
{
y = next[y];
}
}
return y==m ? x-y : -1;
}
|
四、扩展用例
1.另一棵树的子树
leetCode 572 Easy
题目地址
（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
|
class Solution {
public:
static bool same(TreeNode *a, TreeNode *b)
{
if(a==nullptr && b == nullptr)
{
return true;
}
if(a!=nullptr && b!=nullptr)
{
return a->val == b->val && same(a->left, b->left)
&& same(a->right , b->right);
}
return false;
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root != nullptr && subRoot != nullptr)
{
return same(root, subRoot) || isSubtree(root->left, subRoot)
|| isSubtree(root->right, subRoot);
}
return subRoot == nullptr;
}
};
|
（2）对二叉树进行先序序列化，在使用KMP算法进行匹配
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
| struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution {
public:
static void serial(TreeNode *root, vector<string> &path)
{
if(root == nullptr)
{
path.push_back("null");
}
else
{
path.push_back(root->val);
serial(root->left,path);
serial(root->right, path);
}
}
static vector<int> get_next(vector<string> s2)
{
int size = s2.size();
vector<int> next(size);
if(size > 2)
{
next[0] = -1;
next[1] = 0;
}
else if(size == 2)
{
next[0] = -1;
next[1] = 0;
return next;
}
else
{
next[0] = -1;
return next;
}
int i = 2, cn=0;
while(i<size)
{
if(s2[i-1] == s2[cn])
{
next[i] = ++cn;
i++;
}
else if(cn > 0)
{
cn = next[cn];
}
else
{
next[i] = 0;
i++;
}
}
return next;
}
static int kmp(vector<string> s1, vector<string> s2)
{
int n = s1.size();
int m = s2.size();
int x = 0, y=0;
vector<int> next = get_next(s2);
while(x<n && y<m)
{
if(s1[x] == s2[y])
{
x++;
y++;
}
else if(y==0)
{
x++;
}
else
{
y = next[y];
}
}
return y==m ? x-y : -1;
}
bool isSubtree(TreeNode* root, TreeNode* subRoot) {
if(root != nullptr && subRoot!= nullptr)
{
vector<string> s1;
vector<string> s2;
serial(root, s1);
serial(subRoot, s2);
return kmp(s1, s2) !=-1;
}
return subRoot == nullptr;
}
};
|
