串的模式匹配——next函数详解

"第4章 串 - 数据结构" 在计算机科学中，"串"（或字符串）是字符的有限序列，可以是空串（表示为Ф）。串的长度是它包含的字符数量。例如，"abcde"的长度是5。串可以用"a1a2…an"的形式表示，其中每个ai代表一个字符，双引号用于区分串与其他标识符。 串的相等性是基于它们的长度和对应位置的字符是否相同。只有当这两个条件都满足时，两个串才被认为是相等的。子串是串中的连续字符子序列，"abcde"的子串包括"abcde"自身以及它的所有真子串，如"","a","ab","abc","abcd"等。计算一个串的所有真子串数量，可以采用数学公式推广，如"abcde"有15个真子串。 串的基本运算包括： 1. StrAssign(&s,cstr)：将字符串常量cstr赋值给串s。 2. StrCopy(&s,t)：将串t复制给串s。 3. StrEqual(s,t)：判断s和t是否相等，相等返回真，否则返回假。 4. StrLength(s)：返回串s的长度。 5. Concat(s,t)：将s和t连接成一个新的串。 6. SubStr(s,i,j)：从s中提取从第i个字符开始的长度为j的子串。 7. InsStr(s1,i,s2)：在s1的第i个位置插入s2。 8. DelStr(s,i,j)：从s中删除从第i个字符开始的长度为j的子串。 9. RepStr(s,i,j,t)：将s中从第i个字符开始的j个字符替换为t。 10. DispStr(s)：输出串s的所有字符。 在串的存储结构中，主要有两种常见方式：顺序存储和链式存储。顺序存储是将串的字符连续存储在内存中，类似于数组。这种存储方式便于进行基本操作，例如实现上述的串操作。例如，StrLength(s)可以通过访问串的最后一个字符的位置来快速计算。然而，插入和删除操作可能需要移动大量字符，效率相对较低。 在本章中，还提到了"next[j]"函数，这是一个在模式匹配算法（如KMP算法）中使用的辅助数组。next[j]的值表示在模式串中，最长的前缀和后缀相同的子串的长度，如果不存在这样的子串，则next[j]为0。对于给定的例子"abab"，其next数组为[-1, 0, 0, 1]。这个数组在模式匹配时能帮助我们避免不必要的字符比较，提高效率。 串的模式匹配是查找一个字符串（目标串）中是否存在另一个字符串（模式串）的过程。next数组是优化这种匹配的关键工具，它减少了在比较过程中需要回溯的情况，从而提高了算法的性能。 本章总结了串的基本概念、存储结构以及模式匹配中next数组的定义和应用，为后续深入学习字符串处理和文本分析奠定了基础。