字符串
2020-05-17 本文已影响0人
云莉6
概念
是由零个或多个字符组成的有限序列。一般记为 s = a1a2…an (0<=n<=∞)
。它是编程语言中表示文本的数据类型。
实现
参考:https://lemire.me/blog/2017/07/07/are-your-strings-immutable/
在一个面向对象语言把字符串表示为对象的情况下,
- 可变的 mutable:值在运行期可以变更;
- 不变的 immutable:值在创建后就不可变更了。
字符串不可变的语言:
- Java
- C#
- JavaScript
- Go
字符串可变的语言:
- Ruby
- PHP
对字符串可变性限制弱的语言:
- C、C++ 用 const 限定字符串不可变,也可以不限定
- Swift 用 let 限定字符串不可变,也可以不限定
字符串定义
Python
x = ‘abbc’
x = “abbc"
Java
String x = “abbc”;
C++
string x(“abbc”);
字符串遍历
Python
for ch in “abbc”:
print(ch)
Java
String x = “abbc”;
for (int i = 0; i < x.size(); ++i) {
char ch = x.charAt(i);
}
for ch in x.toCharArray() {
System.out.println(ch);
}
C++
string x(“abbc”);
for (int i = 0; i < s1.length(); i++) {
cout << x[i];
}
字符串比较
Java
String x = “abb”;
String y = “abb”;
x == y —-> false
x.equals(y) —-> true
x.equalsIgnoreCase(y) —-> true
字符串匹配算法
-
暴力法(brute force)- O(mn)
-
Rabin-Karp 算法
在朴素算法中,我们需要挨个比较所有字符,才知道目标字符串中是否包含子串。 为了避免挨个字符对目标字符串和子串进行比较,我们可以尝试一次性判断两者是否相等。因此,我们需要一个好的哈希函数(hash function)。通过哈希函数,我们可以算出子串的哈希值,然后将它和目标字符串中的子串的哈希值进行比较。这个新方法在速度上比暴力法有显著提升。 Rabin-Karp 算法 的思想: 1. 假设子串的长度为 M(pat),目标字符串的长度为 N(txt); 2. 计算子串的 hash 值 hash_pat; 3. 计算目标字符串 txt 中每个长度为 M 的子串的 hash 值(共需要计算 N-M+1 次) 4. 比较 hash 值:如果 hash 值不同,字符串必然不匹配;如果 hash 值相同,还需要使用朴素算法再次判断。
-
KMP 算法
Knuth-Morris-Pratt KMP 的思想是,当子串与目标字符串不匹配时,其实你已经知道了前面已经匹配成功的那一步部分字符(包括子串和目标字符串),设法利用这个已知信息,不要把“搜索位置”移回比较过的位置,继续把它后移,这样就提高了效率。
参考链接:
-
Boyer-Moore 算法:https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html
-
Sunday 算法:https://blog.csdn.net/u012505432/article/details/52210975