串(string)(或字符串)是由零个或者多个字符组成的有限序列。

串的表示和实现

定长顺序存储表示

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。 在串的定长顺序存储结构中,按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区。 串的实际长度可在这预定义长度的范围内随意,超过预定义长度的串值则会被舍弃,称之为”截断”。

堆分配存储表示

以一组地址连续的存储单元存放串值字符序列,但它们的存储空间是在程序执行过程中动态分配而得。在C语言中, 存在一个称之为”堆”的自由存储区,并由C语言的动态分配函数malloc()free()来管理。

串的块链存储表示

和线性表的链式存储结构相似,也可以采用链表方式存储串值。由于串结构的特殊性,串结构中的每个数据元素是一个字符,则 用链表存储串值时,存在一个”结点大小”的问题,即每个结点可以存放一个字符,也可以存放多个字符。

串的模式匹配算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function index(fatStr,sonStr){
var fatStrLen = fatStr.length,
sonStrLen = sonStr.length,
gap = fatStrLen - sonStrLen,
i = 0;
while (i<=gap) {
for (var j = 0; j < sonStrLen; j++) {
if (fatStr.charAt(i+j)!==sonStr.charAt(j)) {
break;
}
}
if (j === sonStrLen) {
return i;
}else {
i++;
}
}
return -1;
}

模式匹配的一种改进算法

这种改进算法是 克努特,莫里斯,普拉特三人同时发现的,因此简称其为KMP算法。 这种算法的改进在于每当一趟匹配过程中出现字符比较不等时,不需要回溯,而是利用已经得到的”部分匹配”的结果将模式 向右滑动尽可能远的一段距离后,继续进行比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
function kmpGetNext(str) {
var len = str.length,
next = [0];
for (var i = 1; i < len; i++) {
var tmp = 0;
for (var j = 0; j < i; j++) {
if (str.slice(0, j + 1) == str.slice(i - j, i + 1)) {
tmp = j + 1;
}
}
next.push(tmp);
}
return next;
}
function kmp(fatStr, sonStr) {
var fatStrLen = fatStr.length,
sonStrLen = sonStr.length,
gap = fatStrLen - sonStrLen,
next = kmpGetNext(sonStr), //替代
i = 0,
j = 0;
while (i <= fatStrLen) {
if (fatStr.charAt(i) == sonStr.charAt(j)) {
i++;
j++;
} else if (j !== 0) {
j = next[j]; //如果j不等于0就让j等于next[j]
} else {
i++; //j等于0,且不匹配,则i主串向右划
}
if (j === sonStrLen - 1) { //当完全匹配时,返回i-j,即子串对应的序号
return i - j;
}
}
return -1;
}
分享 留言