|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
串是仅由字符构成的有限序列，是取值范围受限的线性表。一般记为S='a1a2…an'，其中S是串名，a1a2…an是串值。
|
|
|
|
|
|
|
|
|
|
（3）子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串。子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。
|
|
|
|
（4）串相等：指两个串长度相等且对应位置上的字符也相同。
|
|
|
|
（5）串比较：两个串比较大小时以字符的ASCII码值作为依据。比较操作从两个串的第一个字符开始进行，字符的ASCII码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
串（String）是字符串的简称，是由零个或多个字符组成的有限序列，记为S="a1a2a3…an"。含零个字符的串（Null String）称为空串，用Φ表示。其他串称为非空串。任何串中所含字符的个数称为该串的长度（或串长）。空串的长度为0。
|
|
|
|
串中任意连续的字符组成的子序列称为子串。主串是包含子串的串。两个串相等，当且仅当两个串值相等，即长度、位置都相等。空格也是串集合中的一个元素，多个空格组成空格串。
|
|
|
|
在C语言中，串即为字符串。字符串常量是用一对双引号括住若干个字符来表示的。
|
|
|
|
|
|
|
|
|
|
.串赋值strassign（S, chars）：把一个字符串常量赋给串S，即生成一个其值等于chars的串S。
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
串的运算是串的重点和难点，特别是顺序串上子串定位的运算。
|
|
|
|
子串定位运算又称串的"模式匹配"或"串匹配"，即在主串中查找出子串出现的位置，实际应用中非常广泛，如文本编辑中的"查找和替换"用到的就是子串定位运算的算法。
|
|
|
|
在串匹配中，将主串称为目标（串），子串称为模式（串），子串如同一个模板（样本），用其在目标上从头往后比较查找，若找到和子串一样的一个连续子序列，则称匹配成功，并返回其相应的起始位置。
|
|
|
|
经典的模式匹配算法——Brute-Force的思想是：从目标串s=s0s1…Sn-1的第一个字符开始和模式串t=t0t1…tm-1中的第一个字符比较，若相等，则继续逐个比较后继字符；否则，从目标串s的第二个字符开始重新与模式串t的第一个字符进行比较，依次类推。若存在模式串的每个字符依次和目标串中的一个连续字符序列相等，则匹配成功，函数返回模式串t中第一个字符在主串s中的位置；否则匹配失败，函数返回-1。
|
|
|
|
Brute-Force算法在进行模式匹配过程中，指向主串的指针经常回溯，因而在某些情况下时间复杂度较高，为此，提出了KMP算法。
|
|
|
|
KMP算法是由D.E.Knuth、J.H.Morris和V.R.Pratt共同提出的，所以称为Knuth-Morris-Pratt算法，简称KMP算法。该算法比Brute-Force算法有较大改进，主要是消除了主串指针的回溯，从而使算法效率有一定程度的提高。
|
|
|
|
设s=s0s1…sn-1，t=t0t1…tm-1，当si≠tj(0≤i≤n-m, 0≤j
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
