什么是串？
其实串就是我们日常所说的字符串，它是一系列结点组成的一个线性表，每一个结点存储一个字符。我们知道C语言里并没有字符串这种数据类型，而是利用字符数组加以特殊处理（末尾加'\0'）来表示一个字符串，事实上数据结构里的串就是一个存储了字符的链表，并且封装实现了各种字符串的常用操作。
关于Java String 的一些问题
public static void main(String[] args) {
System.out.println(substring("张三"));
}
public static String substring(String str){
//剪切字符串
str.substring(1, str.length());
return str;
}
上图输出结果是什么？
String StringBuilder StringBuffer 又有什么区别？
为什么字符串拼接的时候推荐使用StringBuilder？
不要慌，我们现在来了解数据结构之串
String、StringBuilder、StringBuffer类源码分析
String
public final class String
implements java.io.Serializable, Comparable<String>, CharSequence {
/** The value is used for character storage. */
private final char value[];
比较重要的两个部分，String是一个终态类，不允许继承，value字段也是常量，不允许改变，从这一点就已经可以看出我们对字符串的插入、截取等功能其实不是在原有的字符串上操作的。
比如字符串A+字符串B，用String实现其实是，先创建一个字符串C，然后再吧字符串A和B放到C
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
//获取查询字符串的第一个字符
char first = target[targetOffset];
//匹配的最大次数
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
if (source[i] != first) {
//匹配第一个字符是否相等
while (++i <= max && source[i] != first);
}
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j]
== target[k]; j++, k++);
//从第一个字符开始，所有字符都相等，说明匹配成功
if (j == end) {
return i - sourceOffset;
}
}
}
//不存在返回-1
return -1;
}
以上是对indexOf方法做的一些简单说明，解释的话上面注释已经写清楚了
StringBuilder
我们进入StringBuilder的继承类AbstractStringBuilder
abstract class AbstractStringBuilder implements Appendable, CharSequence {
//跟String不一样的就是这里不是常量的
char[] value;
//多了一个count
int count;
AbstractStringBuilder() {
}
AbstractStringBuilder(int capacity) {
value = new char[capacity];
}
@Override
public int length() {
return count;
}
从上面的代码上，我们可以大致了解到，StringBuilder是由一个非常量字符数组成的
接下来我们再看看StringBuilder的append方法
public AbstractStringBuilder append(String str) {
if (str == null)
return appendNull();
//获取追加字符的长度
int len = str.length();
//确保追加的字符串有足够的空间
ensureCapacityInternal(count + len);
str.getChars(0, len, value, count);
count += len;
return this;
}
StringBuffer
StringBuffer和StringBuilder非常相似，唯一不一样的在于，StringBuffer是线程安全的，因为它每个方法都加了synchronized，比如
public synchronized int length() {
return count;
}
总结
做Java经常会听说多字符串拼接的时候用StringBuilder能提高效率，从上面的分析可以看出，String进行字符串拼接的时候，首先需要生成一个两个字符串相加之和大小的字符串，然后再把这两个字符串写入的新的字符串中，这种方式的优点是操作简单，但是内存消耗严重，StringBuilder就不一样了，初始化的字符数组是可变的，拼接的时候发现存储空间不够的情况会自动扩容，拼接操作在原有的字符串上进行的。
字符搜索KMP算法
S1: A B C D E F A B C
S2: E F A
搜索S1中是否包含S2
朴素匹配算法
算法复杂度O(n*m)
KMP算法
这文章里面已经有比较完全的解答了
https://segmentfault.com/a/1190000008575379
总结的一些关键信息
最核心的其实就是匹配开头的字符串
next数组存储的其实就是第一个字符开头
KMP算法的根本其实就是不需要想暴力匹配一样全部回退，只需要回退到跟搜索字符相同开头的字符就可以了
ABCDABCEABCA
ABCA
当我们匹配到了ABC之后，发现D不对，其实这种情况下，不用回退到第一个重新匹配，只要找到刚刚匹配的ABC中找到A开头的开始就可以了，next数组就是帮我们实现这一点的
算法复杂度O(n+m)
网友评论