串
串是有零个或多个字符组成的有限序列，又名为字符串
空串：0个字符的串
空格串：只包含空格的串
串的比较
给定两个串：s=“a1a2…an”，t=“b1b2…bm”，当满足以下条件之一时，s<t。
- n<m，且ai = bi (i=1,2,...,n)
- 示例 s=“hap” t="happy"
- 存在某个k≤min(m,n) ，使得ai=bi (i=1,2,...,k-1),ak < bk
- 示例 s=“happen” t="happy" s5='e' < t5='y'
串的抽象数据类型
对于不同的高级语言，其实对串的基本操作会有不同的定义方法，
所以在用某个语言操作字符串时，需要先查看它的参考手册关于字符串的基本操作有哪些。
Java中，字符串操作就还有
-
ToLower转小写
-
ToUpper转大写
-
IndexOf从左查找子串位置
-
LastIndexOf从右查找子串位置
-
Trim去除两边空格等
串的顺序存储结构
用一组地址连续的存储单元，一般是定长的数组。
于是对于串的顺序存储，有一些变化，串值的存储空间可在程序执行过程中动态分配而得。
比如在计算机中存在一个自由存储区，叫做“堆”。
这个堆可由C语言的动态分配函数 malloc（）和free（）来管理。
串的链式存储结构
与链表非常相似，但串结构的特殊性，一个结点应该考虑存放多个字符
最后一个结点未被占满时，用指定字符补全。
总的来说，串的链式存储不如顺序存储灵活，性能也不如顺序存储结构好。
串的模式匹配
最重要的操作：子串匹配
假设我们要从主串S = "goodgoogle"中，找到子串T = "google"的位置。
常规算法
思想：对主串S做大循环，对子串T做小循环，直到匹配成功或全部遍历。
步骤如下：
-
主串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个字母全匹配，匹配成功
代码实现
package com.string;
/**
* 字符串匹配的常规算法
*/
public class Match {
public static void main(String[] args) {
String S = "goodgoogle";
String T = "google";
int res = match(S, T, 0);
System.out.println(res);
res = match(S, T, 5);
System.out.println(res);
}
public static int match(String text, String pattern, int pos) {
char[] s = text.toCharArray();
char[] t = pattern.toCharArray();
// pos主串开始匹配的位置
for (int i = pos; i < s.length; i++) {
for (int j = 0; j < t.length; j++) {
if (t[j] != s[i + j]) {
break;
}
// 如果匹配到最后一个字母且相等，说明匹配成功！
if (j == t.length - 1 && t[j] == s[i + j]) {
return i;
}
}
}
// 匹配失败
return -1;
}
}
结果
4
-1
算法分析
KMP算法
用next数组解决了以上问题，详细到后面学算法再深究。
《大话数据结构》5.7节 KMP算法
《算法导论》第二版第32章
总结回顾
串（string）是由零个或多个字符组成的有限序列，又名叫字符串。
本质上，它是一种线性表的扩展，但相对于线性表关注一个个元素来说，
我们对串这种结构更多的是关注它子串的应用问题，如查找、替换等操作。