大话数据结构 - 串

1. 串的定义

串是由0个或多个字符组成的有限序列，也叫做字符串。串中 字符数目n称为串的长度。

子串：串中任意个数的连续字符组成的子序列称为该字符串的子串，包含该子串的串称为主串。子串中的位置就是该子串第一个字符在主串中的序号。

2. 串的比较

计算机的字符串标准包括：ASCII码和Unicode码。其中ASCII由8位二进制组成，可以表达256个字符；Unicode由16位二进制组成，可以表达65536个字符。当然unicode前面256个字符与ASCII一致。

3. 串的抽象数据类型

串的逻辑结构和线性表很相似，不同之处在于串针对的是字符。

4. 串的存储结构

串的存储结构与线性表相同，分为两种：顺序存储结构，链式存储结构。

4.1 串的顺序存储结构

串的顺序存储结构使用数组来存储，字符串的实际长度通可以存在数组的第一个位置，最后一个位置等。顺序存储结构的最大缺点在于字符串在进行一个操作，比如字符串合并等可能会导致溢出，字符串的长度超过数组长度。

4.2 串的链式存储结构

串的链式存储结构与链表类似，不同之处在于每个节点可能存储多个字符。

5. 朴素的模式匹配算法

简单的讲，字符串匹配最简单的目的就是找某个字符串中是否包含另外一个字符串，如果包含则返回位置。比如在Python中有这样find函数来实现功能。

# -*- coding: utf-8 -*-

str_m = "abaababaddecab"    # 母串
str_s = "abad"      # 子串

pos = str_m.find(str_s)

6.KMP模式匹配算法

reference：

http://www.cnblogs.com/c-cloud/p/3224788.html

http://www.cnblogs.com/huangxincheng/archive/2012/12/01/2796993.html