[科普中国]-有限长度串

简介

一串邻接的字符就组成字符串。在程序设计语言中构成字和各种标识符。如程序名、各种定义符、各种控制命令等。可以用在BASIC语言的注释语句中对程序予以注解，或其他语言的注释部分。字符串也可以作为字符数据，接受计算机系统的处理2。在配有适当软件的微机上，汉字也可作为字符进行处理。简单的图形也能定义为特殊的字符或字符串。有限长度串是指串（字符串）的长度是有限的。其中有限是十分重要的，有限长度串在很多方面都有应用。如，在数据库中，定义字符数据长度时，一般要确定字符数据长度。在形式语言理论中，有限长度串也有重要应用。

形式理论形式语言理论是用数学方法研究自然语言(如英语)和人工语言(如程序设计语言)的语法的理论。它只研究语言的组成规则，不研究语言的含义。形式语言理论在自然语言的理解和翻译、计算机语言的描述和编译、社会和自然现象的模拟等方面有广泛的应用。在形式语言理论中，在构造有关形式文法和自动机过程中，会用到有限长度串，常见形式如下。

设 Σ 是叫做字母表的非空有限集合。Σ 的元素叫做“符号”或“字符”。在 Σ 上的字符串(或字)是来自 Σ 的任何有限序列。例如，如果 Σ = {0, 1}，则 0101 是在 Σ 之上的字符串。

字符串的长度是在字符串中字符的数目(序列的长度)，它可以是任何非负整数。“空串”是在 Σ 上的唯一的长度为 0 的字符串，并被指示为 ε 或 λ。

在 Σ 上的所有长度为 n 的字符串的集合指示为 Σn。例如，如果 Σ = {0, 1} 则 Σ2 = {00, 01, 10, 11}。注意 Σ0 = {ε} 对于任何字母表 Σ。

在 Σ 上的所有任何长度的字符串的集合是 Σ 的Kleene闭包并被指示为 Σ*。 例如，如果 Σ = {0, 1} 则 Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, …}。尽管 Σ* 自身是可数无限的，Σ* 的所有元素都有有限长度。

在 Σ 上一个字符串的集合(就是 Σ* 的任何子集)被称为在 Σ 上的形式语言。例如，如果 Σ = {0, 1}，则带有偶数个零的字符串的集合({ε, 1, 00, 11, 001, 010, 100, 111, 0000, 0011, 0101, 0110, 1001, 1010, 1100, 1111, …})是在 Σ 上的形式语言。

字符串分析字符串分析是用于判定软件程序中给定字符串变量(一般称为热点变量)的某些性质的程序分析。与针对数值变量的程序分析相比,字符串分析必须处理字符串变量的两个特性：

首先，字符串变量的值域与数值变量不同：数值变量的值域是一个数值集合，通常可以表示为数轴上若干个离散的点或连续区间；而字符串变量的值域是一个字符串集合,需要一个形式化的符号系统(例如正则语言)准确地描述这一字符串集合；

其次，字符串变量上定义的操作(拼接、字符替换等)与数值变量上的操作不同，因此需要准确地确定这些操作会对字符串变量上所关注的性质产生怎样的影响,即对于这些字符串操作，已知操作数的性质,如何确定操作结果的性质。

对字符串变量这两个特性的处理，即字符串变量值域的抽象表示和字符串操作的处理方式是字符串分析与传统的针对数值变量的程序分析的主要区别。

函数应用1. 连接运算 concat(s1,s2,s3…sn) 相当于s1+s2+s3+…+sn。

例：concat(‘11’,'aa’)='11aa’;

2. 求子串。 Copy(s,I,I) 从字符串s中截取第I个字符开始后的长度为l的子串。

例:copy(‘abdag’,2,3)=’bda’

3. 删除子串。过程 Delete(s,I,l) 从字符串s中删除第I个字符开始后的长度为l的子串。

例：s:=’abcde’;delete(s,2,3);结果s:=’ae’

4. 插入子串。 过程Insert(s1,s2,I) 把s1插入到s2的第I个位置

例：s:=abc;insert(‘12’,s,2);结果s:=’a12bc’

5. 求字符串长度 length(s) 例：length(‘12abc’)=5

在ASP中 求字符串长度用 len(s)例: len("abc12")=5

6. 搜索子串的位置 pos(s1,s2) 如果s1是s2的子串 ，则返回s1的第一个字符在s2中的位置，若不是子串，则返回0.

例：pos(‘ab’,’12abcd’)=3

7. 字符的大写转换。Upcase(ch) 求字符ch的大写体。

例：upcase(‘a’)=’A’

8. 数值转换为数串。 过程 Str(x,s) 把数值x化为数串s.

例：str(12345,s); 结果s=’12345’

9. 数串转换为数值。 过程val(s,x,I) 把数串s转化为数值x,如果成功则I=0,不成功则I为无效字符的序数,第三个参数也可不传

例：val(‘1234’,x,I);结果 x:=1234