串及串匹配-cis_orcad本地数据库配置方法

§11.1串及串匹配11.1.1串字符串一般地，由n个字符构成的串记作S = "a0 a1 ... an-1"，其中ai  ，0  i < n。这里的是所有可用字符的集合，称作字符表（alphabet）。常见的字符表有ASCII字符集或Unicode字符集；就二进制表示形式而言，字符表 = {0, 1}；而在生物信息学中，则可能是构成DNA序列的所有碱基，或者组成蛋白质的所有氨基酸。字符串S所含字符的总数n，称作S的长度，记作|S| = n。这里只考虑长度有限的串，即n < 。特别地，长度为零的串称作空串（null string）。请注意，空串并非由空格字符'□'组成的串，二者完全不同。 子串字符串中任一连续的片段，称作其子串（substring）。具体地，对于任意的0  i + k < n，由字符串S中起始于位置i的连续k个字符组成的子串记作： substr(S, i, k) = "ai ai+1 ... ai+k-1" = S[i, i+k)有两种特殊子串：起始于位置0、长度为k的子串称为前缀（prefix），而终止于位置n-1、长度为k的子串称为后缀（suffix），分别记作： prefix(S, k) = substr(S, 0, k) = S[0, k) suffix(S, k) = substr(S, n-k, k) = S[n-k, n)由上述定义可直接导出以下结论：空串是任何字符串的子串，也是任何字符串的前缀和后缀；任何字符串都是自己的子串，也是自己的前缀和后缀。此类子串、前缀和后缀分别称作平凡子串（trivial substring）、平凡前缀（trivial prefix）和平凡后缀（trivial suffix）。反之，字符串本身之外的所有非空子串、前缀和后缀，分别称作真子串（proper substring）、真前缀（proper prefix）和真后缀（proper suffix）。