字符串

概念

是由零个或多个字符组成的有限序列。一般记为 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  的思想是，当子串与目标字符串不匹配时，其实你已经知道了前面已经匹配成功的那一步部分字符（包括子串和目标字符串），设法利用这个已知信息，不要把“搜索位置”移回比较过的位置，继续把它后移，这样就提高了效率。
  

  参考链接：

  • https://www.bilibili.com/video/av11866460?from=search&seid=17425875345653862171
  • http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html

• Boyer-Moore 算法：https://www.ruanyifeng.com/blog/2013/05/boyer-moore_string_search_algorithm.html

• Sunday 算法：https://blog.csdn.net/u012505432/article/details/52210975