串

2016年11月23日

16:52

串类型的定义

串（string）是由零个或多个字符组成的有限序列，一般记为

s = 'a1a2a3a4.....an'（n>= 0)

s是串的名，单引号括起来的值是串的值；ai（1<=i<=n）可以是字幕数字或其他字符；串中n的长度称为串的长度。零个字符的串称为空串（null string）。

串中任意个连续的字符组成的子序列称为该串的子串。

两个串是相等的，当且仅当这两个串的值相等。

由一个或多个空格组成的串叫空格串。

存储密度串值所占的存储位置实际分配的存储位

字符串匹配算法：

KMP算法：

int KMP(String s,string T,int pos)

//利用模式串T的next函数求T在主串S中第pos个字符之后的位置的KMP算法。其中T非空，1《pos《StrLength(s)

{

i = pos;

J = 1;

While(i <= S[0]&&j <= T[o])

{

if(j == 0||S[i] == T[j])

{

++i;

++j;

}

else

j = next[j];

}

if(j > T[0])

return i - T[0];

else

return 0

}

其中next数组的求法

已使用 Microsoft OneNote 2016 创建。