[科普中国]-字符数组子串引用

简介

数组是一种特殊的对象类型，其中可以保存一个有序的元素集合1。数组元素的类型 称为该数组的基类型(base type)；其中保存的元素个数是一个固定的属性，称为其长度(length)。字符数组子串引用是指应用程序对字符数组中子串的引用。在实际应用中，有时候需要对字符串一个子串进行引用，来判断这个字符数组是否满足需求。字符数组子串引用需要对字符数组中字符串经过查找匹配等过程，其中匹配算法的好坏直接影响字符数组子串引用的性能，例如时间代价、空间代价。

有关术语字符变量字符常数的一般形式是由一对单引号‘ ’或一对双引号“”限定的一串字符。字符串中的字符，允许是PORTRAN字符集的任意字符，如果系统还支持其它字符，例如汉字、希腊字、化学符号、数学符号，也可引入字符串内，用一对‘ ’或“”界定。

字符型数据除了有类型、种别外，比其它类型还多了一个长度特性，即规定它有几个字符数。字符型说明语句的关键字是CHARACTER，其长度说明方法是紧跟在CHARACTER后面写一对括号，括号内写LEN=字符长度。其一般形式是：

CHARACTER[(LEN=整型字符长度表达式[,KIND=种别值])][,属性说明] ::变量名表[=初始值]

其中LEN后面的整常数表达式规定被说明字符变量长度，为正整数，LEN的参数与KIND的参数都写在括号内，次序可以任意。在字符型说明语句中，长度说明必须有，不可省略，种别参数可以省略，此时取标准值。仅有关键字CHARACTER而没有括号时认为字符是一个字节长。可以省去LEN=及KTND=，只写参数值，此时字符长度必须写在前面。只有长度说明的语句可分为有括号和无括号两种，例如：

CHARACTER(LEN=12,KIND=1) :: A,B

CHARACTER(KIND=1,LEN=12) :: A,B

CHARACTER(12,1) :: A,B

CHARACTER*12 :: A,B

都是等价的，前者说明X、Y2是字符型变量，种别参数为3．每个变量长度为12。后者说明表明长度为12，种别值为1。

长度也可以写成一个*号，表示长度暂不确定，待以后与程序中实际需要的长度相一致。例如：

CHARACTER(LEN=*),PARAMETER :: C_NAME=‘GIRL’

CHARACTER(LEN=*),PARAMETER :: C_NAME=‘BOY’

都是合法的说明语句，说明字符常量C_NAME，前者长度为4，后者长度为3。

用字符型变量作为过程的哑元时，可以用正整数作长度，也可以把*作长度，后者可以与任何长度的实元作哑实结合，相当于以实元的具体长度为哑元的长度。

CHARACTER后面说明的长度是其后所有实体名的公共长度，如果某一变量的长度与其它不同，可以在其变量名后标出自己的特有长度，方法是在变量名后写上*及长度。例加：

CHARACTER(LEN=12) :: A,B*5,C,D*7,E

字符子串字符数据中某一部分相连的字符为字符子串，也可以作为一个实体与字符变量一样参加操作。字符子串的一般形式是：V(e1:e2)。V是字符型实体名，包括字符变量名、字符函数名、字符数组元素等等。e1,e2是整型表达式或正整常数，e1的值指明子串在V中的起始列号，e2的值指明子串在V中的终止列号。如果e1省略，表示子串从第一个字符取起；e2省略，表示子串取到末尾；如e1,e2都省略，表示子串从头取到尾。例如：设有字符变量A，其取值为‘ABCDE12345FGH’，则下面的子串取值为：

A(3:11)->‘CDE12345F’，

A(I+4:9)->‘E1234’(I=1)，‘1234’(I=2)

A(:5)->‘ABCDE’

A(11:)->‘FGH’

A(:)->‘ABCDE12345FGH’

A(3:3)->‘C’

子串在程序中可直接引用，也可被其它字符实体再赋值，因此可使程序员任意地取出一部分字符，并按需要替换一部分字符，非常灵活。例如：PRINT *，(A(I:I+1),I=6,9)，可以打印‘12’、‘23’、‘34’、‘45’。

匹配方法近似匹配近似匹配是一种允许误差的串匹配。这种误差的度量一般用编辑距离，记为k。衡量编辑距离的操作包括插入、删除、替换。问题的输入是文本T，模式P和编辑距离k，输出是匹配数或匹配位置。常用的方法包括动态规划、自动机、位并行和过滤算法。近似匹配也属于Non-standard Stringology问题。它最常见的应用背景来源于生物信息学。问题定义上，近似匹配中的k可以对模式中的任何字符的编辑操作进行计数。例如，给定文本T的子串T’= ……aacct……，P = aaacc，从P到T’要经过两次替换操作，因此k= 2。

朴素的模式匹配算法算法思想：从目标串的的第一个字符起与模式串的第一个字符比较，若相等，则继续对字符进行后续的比较，否则目标串从第二个字符起与模式串的第一个字符重新比较，直至模式串中的每个字符依次和目标串中的一个连续的字符序列相等为止，此时称为匹配成功，否则匹配失败。

若模式子串的长度是m,目标穿的长度是n，这时最坏的情况是每遍比较都在最后出现不等，即没变最多比较m次，最多比较n-m+1遍，总的比较次数最多为m(n-m+1)，因此朴素的模式匹配算法的时间复杂度为O(mn)。朴素的模式匹配算法中存在回溯，这影响到匹配算法的效率，因而朴素的模式匹配算法在实际应用中很少采用。在实际应用主要采用无回溯的匹配算法，KMP算法和BM算法均为无回溯的匹配算法。

KMP匹配算法Knuth-Morris-Pratt算法（简称KMP），是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的一个改进算法，消除了朴素的模式匹配算法中回溯问题，完成串的模式匹配。

算法思想：

设目标串为s，模式串为t， i、j 分别为指示s和t的指针，i、j的初值均为0。

若有 si = tj，则i和j分别增1；否则，i不变，j退回至j=next[j]的位置 ( 也可理解为串s不动，模式串t向右移动到si与tnext[j]对齐 )；

比较si和tj。若相等则指针各增1；否则 j 再退回到下一个j=next[j]的位置(即模式串继续向右移动 )，再比较 si和tj。

依次类推，直到下列两种情况之一：

1)j退回到某个j=next[j]时有 si = tj，则指针各增1，继续匹配；

2)j退回至 j=-1，此时令指针各增l，即下一次比较 si+1和 t0。

记模式P的长度为m,目标T的长度为n,则KMP匹配算法的时间复杂度的分析如下：

整个匹配算法由Find()和GenKMPNext()两部分算法组成。在Find()中包含一个循环,J的初值为0，每循环一次j的值严格家1，指导j等于n时循环结束，故循环执行了n次。在GenKMPNext()中，表面上有两重循环，时间复杂度似乎为O(),其实不然，GenKMPNext()的外层循环恰好执行了m-1次；另外，j的初值为-1，外层循环中，每循环一次，j的值就加1，同时，在内层循环中j减小，但最少不会小于-1，因此内层循环中j=next[j]的语句的总的执行次数应小于或等于j的值在外层循环中被加2 的次数。即在算法GenKMPNext()结束时，j=next[j]的执行总次数小于等于m-1次。

综上，对于长度为m的模式和长度为n的目标T的模式匹配，KMP算法的时间复杂度为O(m+n)。

Boyer-Moore字符串搜索算法Boyer-Moore字符串搜索算法是一种非常高效的字符串搜索算法。它由Bob Boyer和J Strother Moore设计于1977年。此算法仅对搜索目标字符串（关键字）进行预处理，而非被搜索的字符串。虽然Boyer-Moore算法的执行时间同样线性依赖于被搜索字符串的大小，但是通常仅为其它算法的一小部分：它不需要对被搜索的字符串中的字符进行逐一比较，而会跳过其中某些部分。通常搜索关键字越长，算法速度越快。它的效率来自于这样的事实：对于每一次失败的匹配尝试，算法都能够使用这些信息来排除尽可能多的无法匹配的位置。定义如下：

S[i]为字符串S从1开始排列的第i个字符

S[i..j]为字符串S的一个子串，始于i，终于j。

S的前缀定义为S[1..i],1