【数据结构】串

串的存储结构
串的基本操作
串的模式匹配
- BF算法
- KMP算法

串的存储结构

定长顺序存储表示

基本概念：
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，为每个串变量分配一个固定长度的存储区，即定长数组。
存储结构：

#define MAXLEN 255  //预定义最大串长为255
typedef struct {
    char ch[MAXLEN];//每个分量存储一个字符
    int length;     //串的实际长度
}SString;   //Sequential String

缺点：只能定长

堆分配存储表示

基本概念：
堆分配存储表示仍然以一组地址连续的存储单元存放串值得字符序列，但它们的存储空间是在程序执行过程中动态分配（堆分配）得到的。
存储结构：

typedef struct {
    char *ch;   //按串长分配存储区
    int length; //串的长度
}HString;   //Heap String

块链存储表示

基本概念：
类似于线性表的链式存储结构，也可采用链表方式存储串值。由于串的特殊性（每个元素只有一个字符），在具体实现时，每个结点既可以存放一个字符，又可以存放多个字符。每个结点称为块，整个链表称为块链结构。

串的基本操作

String类用来存储字符串。
例如：

String a = "Hello";

字符串连接

可以直接用+号，如

String a = "Hello"; 
String b = "world"; 
System.out.println(a + ", " + b + "!"); // output "Hello, world!"

字符串查找

String提供了两种查找字符串的方法，即 indexOf() 与 lastIndexOf() 方法。

indexOf(String s)：用于返回参数字符串 s 在指定字符串中首次出现的索引位置
当调用字符串的indexOf()方法时，会从当前字符串的开始位置搜索 s 的位置。
- 如果没有检索到字符串 s，该方法返回-1
```
String str ="We are students";
int size = str.indexOf("a"); // 变量 size 的值是 3 
```
lastIndexOf(String str)：用于返回字符串最后一次出现的索引位置。
当调用字符串的lastIndexOf()方法时，会从当前字符串的开始位置检索参数字符串 str，并将最后一次出现 str 的索引位置返回。
- 如果没有检索到字符串 str，该方法返回-1。
- 如果lastIndexOf()方法中的参数是空字符串""，则返回的结果与 length 方法的返回结果相同。

获取指定索引位置的字符

使用charAt()方法可将指定索引处的字符返回。

String str = "Hello world";
char mychar = str.charAt(5); // mychar 的结果是 w

获取子字符串

通过String类的substring()方法可对字符串进行截取。

这些方法的共同点就是都利用字符串的下标进行截取，且应明确字符串下标是从 0 开始的。在字符串中空格占用一个索引位置。

substring(int beginIndex)：从begin开始，到结尾结束

String str = "Hello world";
String substr = str.substring(3); //获取字符串，此时 substr 值为 lo world

substring(int beginIndex, int endIndex)：begin和end区间是前闭后开的，[begin, end)

注意：其实这个区间前闭后开是针对字符来说的，看下面举的例子，0~3截取了Hel这三个字符，即 [0, 3)，第0、1、2个字符。
- beginIndex：开始截取子字符串的索引位置
- endIndex：子字符串在整个字符串中的结束位置
理解：但是，我们可以从存储机制去理解它。
Hello World 在系统里是这样存储的：

我们截取了地址0~3，所以截取了Hel这三个字符。
```
String str = "Hello world";
String substr = str.substring(0,3); //substr 的值为 Hel
```

去除空格

trim()方法返回字符串的副本，清除了左右两端的空格。

String str = "        hello           ";
System.out.println(str.trim());
//程序运行结果：hello

字符串替换

replace(String oldChar，String newChar)方法可实现将指定的字符或字符串替换成新的字符或字符串。

oldChar：要替换的字符或字符串
newChar：用于替换原来字符串的内容

注意：如果要替换的字符 oldChar 在字符串中重复出现多次，replace()方法会将所有 oldChar 全部替换成 newChar。需要注意的是，要替换的字符 oldChar 的大小写要与原字符串中字符的大小写保持一致。

String str= "address";
String newstr = str.replace("a", "A");// newstr 的值为 Address

判断字符串是否相等（切不可使用==）

equals(String otherstr)：
如果两个字符串具有相同的字符和长度，则使用equals()方法比较时，返回 true。

注意：equals()方法比较时，区分大小写。
equalsIgnoreCase(String otherstr)：

注意：equalsIgnoreCase()方法与equals()类似，不过在比较时忽略了大小写。

按字典顺序比较两个字符串

compareTo()方法为按字典顺序比较两个字符串，该比较基于字符串中各个字符的 Unicode 值，按字典顺序将此 String 对象表示的字符序列与参数字符串所表示的字符序列进行比较。

如果按字典顺序此 String 对象位于参数字符串之前，则比较结果为一个负整数；
如果按字典顺序此 String 对象位于参数字符串之后，则比较结果为一个正整数；
如果这两个字符串相等，则结果为0.

字母大小写转换

字符串的toLowerCase()方法可将字符串中的所有字符从大写字母改写为小写字母，
而toLowerCaseUpperCase()方法可将字符串中的小写字母改写为大写字母。

str.toLowerCase();
str.toUpperCase();

字符串分割

使用split()方法可以使字符串按指定的分隔字符或字符串对内容进行分割，并将分割后的结果作为字符串数组返回。

str.split(String sign);：sign为分割字符串的分割符，也可以使用正则表达式。

注意：没有统一的对字符串进行分割的符号，如果想定义多个分割符，可使用符号“|”。

例如，“,|=”表示分割符分别为“，”和“=”。

String str = "hello world";
String[] s = str.split(" ");
for(int i=0; i<s.length; i++) {
    System.out.println(s[i]);
}

程序运行结果：

hello
world

串的模式匹配

BF算法

这是一种经典模式匹配算法，暴力破解（Brute-Force）算法
依次比较主串和模式串，若匹配失败，则主串指针回到刚开始比较的位置的下一个位置。

KMP算法

'abab'的前缀：{a,ab,aba}（不包括自己）
'abab'的后缀：{b,ab,bab}（不包括自己）
最长相等前后缀：ab，长度为2

基本概念：
KMP(Knuth、Morris、Pratt三个人名)算法，KMP算法的核心是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是通过一个next()函数实现，函数本身包含了模式串的局部匹配信息。KMP算法的时间复杂度O(m+n)。
操作过程：
KMP算法主要是求解next数组。
next数组中存储的是部分匹配值（即字符串前缀和后缀的最长相等前后缀长度）
[next[j]= egin{cases} 满足p_1...p_i=p_{j-i+1}...p_j的最大i(<j)& ext{最大i，最长相等前后缀长度}\ 0& ext{如果这样的i不存在} end{cases}]
1. 建立next数组；
2. 每次匹配失败，就去找它的next值，令指针j指向next[j]，继续比较。
通俗说明：
若当前部分匹配串的最后一位（即 最长相等后缀的最后一位）匹配失败，那么下一次匹配应该为最长相等前缀中的最后一位。其实很好理解，如果这段匹配失败了，那么就从头开始拿相同的部分（即最长相等前缀）弥补过来，可以省去比较前后缀相同的部分，提高效率。
next数组的计算：

KMP算法中的next函数值只和模式串有关，而和相匹配的主串无关。
- 编号与next数组的关系：next数组的第一个元素值不存在于编号中，即 它用来代表匹配终止，不用跳转比较，前移即可。
  
  即若第一个元素匹配失败，不用跳转到其他元素处重新比较，前移即可，无需跳转到next对应的元素再进行比较。
  
  编号 next
  
  从1开始从0开始
  即 右移+1
  
  从0开始从-1开始
  即 右移不变
1. 首先我们给每个字符标上序号（注意这里序号是从1开始的）
  模式串：abaabcac
  
  序号j 1 2 3 4 5 6 7 8
  
  模式串S a b a a b c a c
2. 之后，我们把模式串的所有前后缀依次列出来，求得每个子串中最长相等前后缀长度maxL（即相等的前缀与后缀的最大长度）
  
  序号j 1 2 3 4 5 6 7 8
  
  模式串S a b a a b c a c
  
  maxL[j] 0 0 1 1 2 0 1 0
3. 将maxL数组右移一位，第一个元素在右移以后空缺，用-1来填充；数组整体+1（右移+1）
  
  序号j 1 2 3 4 5 6 7 8
  
  模式串S a b a a b c a c
  
  maxL[j] 0 0 1 1 2 0 1 0
  
  next[j] 0 1 1 2 2 3 1 2
4. KMP算法的升级版--nextval[]
  1. 首先，第一个值填为0（nextval[1]=0作为特殊标记）
  2. 按序号依次检查maxL值和next值是否相等
    - 若不相等，填入对应next值（nextval[k]=next[k]）（“意见不相同（不等）你就听我的(next)”）
    - 若相等，填入对应序号为next值的nextval值（nextval[k]=nextval[next[k]]）（“意见相同（相等）就一起想一个更好的(nextval[next[k]])”）
  序号j 1 2 3 4 5 6 7 8
  
  模式串S a b a a b c a c
  
  maxL[j] 0 0 1 1 2 0 1 0
  
  next[j] 0 1 1 2 2 3 1 2
  
  nextval[j] 0 1 0 2 1 3 0 2
算法性能：
- 时间效率：O(n+m)
  n为主串长度，m为模式串长度。
  该算法遍历了主串，且避免了回溯。

编号	next
从1开始	从0开始即右移+1
从0开始	从-1开始即右移不变

序号j	1	2	3	4	5	6	7	8
模式串S	a	b	a	a	b	c	a	c
maxL[j]	0	0	1	1	2	0	1	0
next[j]	0	1	1	2	2	3	1	2