东凤网站建设,网页视频下载器安卓破解,建e室内设计网最近有什么活动,怎么做刷会员的网站文章目录 4.3 字符串4.3.1 字符串的定义与存储4.3.2 字符串的基本操作4.3.3 模式匹配算法1. 算法原理2. ADL语言3. 伪代码4. C语言实现5 时间复杂度 4.3 字符串 字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列#xff0c;简称为串。例如 “good morning”就是… 文章目录 4.3 字符串4.3.1 字符串的定义与存储4.3.2 字符串的基本操作4.3.3 模式匹配算法1. 算法原理2. ADL语言3. 伪代码4. C语言实现5 时间复杂度 4.3 字符串 字符串(String)是由零个或多个字符(char)顺序排列组成的有限序列简称为串。例如 “good morning”就是由12个字符构成的一个字符串。一般把字符串记作 S ′ ′ a 0 a 1 … a n − 1 ′ ′ Sa_{0} a_{1}…a_{n-1} S′′a0a1…an−1′′ 其中S是串名引号中的字符序列是串值。字符个数是串的长度长度为0的串被称为空串因为它不包含任何字符。需要注意的是空格字符 并不是空串因为它包含一个字符——空格。 若把某个串称为主串则主串中任意个连续的字符组成的子序列被称为子串。子串在主串中第一次出现时其首字符在主串中的序号被称为该子串在主串中的位置。 关于字符串的基础知识亦可参考前文 【重拾C语言】六、批量数据组织三数组初值字符串、字符数组、字符串数组类型定义 typedef 【重拾C语言】七、指针三指针与字符串字符串与字符串数组指针与字符串的遍历、拷贝、比较反转字符串
4.3.1 字符串的定义与存储 字符串在许多非数值计算问题中扮演着重要的角色并在模式匹配、程序编译和数据处理等领域得到广泛应用。在高级程序设计语言中字符串通常被定义为以特殊字符’\0’称为空字符或字符串结束符结尾的字符序列。这个约定使得在处理字符串时可以方便地确定字符串的结束位置。关于字符串的存储方式主要有两种常见的方式 顺序存储字符串的字符按照顺序依次存储在连续的内存空间中。这种方式使得字符串的访问和操作效率较高可以通过索引直接访问任意位置的字符。在顺序存储方式中字符串的长度可以通过计算字符个数或者遇到’\0’结束符来确定。 链式存储字符串的字符通过链表的方式进行存储。每个节点包含一个字符和指向下一个节点的指针。链式存储方式可以动态地分配内存适用于长度可变的字符串。但是相比于顺序存储链式存储方式需要更多的内存空间并且访问字符需要遍历链表。 选择何种存储方式取决于具体的应用场景和需求。顺序存储适合于需要频繁访问和操作字符串的情况而链式存储适合于长度可变的字符串或者对内存空间要求较高的情况。具体C语言实现可参照前文 【数据结构】数组和字符串十一字符串的定义与存储顺序存储、链式存储及其C语言实现
4.3.2 字符串的基本操作
顺序存储【数据结构】数组和字符串十二顺序存储字符串的基本操作串长统计、查找、复制、插入、删除、串拼接 链式存储【数据结构】数组和字符串十三链式字符串的基本操作串长统计、查找、复制、插入、删除、串拼接
4.3.3 模式匹配算法 文本编辑器中常用的“查找”、“替换”和“全部替换”等基本的编辑操作就是最普通的模式匹配问题即在文本文件中查找串。它的查找过程可简单描述如下给定两个字符串变量 S 和 P其中目标串 S 有n个字符模式串P有m个字符m≤n . 从S的给定位置通常为S的第一个字符开始搜索模式串P如果找到返回模式串P在S中匹配成功的起始位置如果没找到即S中没有P则返回–1 . 字符串匹配可以采用多种算法包括朴素模式匹配算法、KMPKnuth-Morris-Pratt算法、Boyer-Moore算法等。这些算法的性能和效率各不相同具体选择取决于应用的需求和文本数据的规模。
1. 算法原理
从S的字符 S 0 S_{0} S0开始将P长度为m中的字符依次与S中的字符进行比较 若 S 0 P 0 S 1 P 1 … S m − 1 P m − 1 S_{0}P_{0}S_{1}P_{1}…S_{m-1}P_{m-1} S0P0S1P1…Sm−1Pm−1则匹配成功返回与 P 0 P_{0} P0相匹配的字符 S 0 S_{0} S0在 S S S中的位置下标为0若某一步 S i ≠ P i S_{i}≠P_{i} SiPi说明此次匹配不成功以下比较无需进行。 于是再从 S S S的字符 S 1 S_{1} S1开始进行第二次匹配重复刚才的步骤 看是否有 S 1 P 0 S 2 P 1 … S m P m − 1 S_{1}P_{0}S_{2}P_{1}…S_{m}P_{m-1} S1P0S2P1…SmPm−1 若匹配成功返回与P0相匹配的字符S1在S中的下标1.否则从S的字符S2开始进行第三次匹配’ ……若第 n − m 1 n-m1 n−m1次匹配即最后一次匹配仍得不到 S n − m P 0 S n − m 1 P 1 … S n − 1 P m − 1 S_{n-m}P_{0}S_{n-m1}P_{1}…S_{n-1}P_{m-1} Sn−mP0Sn−m1P1…Sn−1Pm−1,说明匹配失败返回 -1 .这种模式匹配算法被称为朴素的模式匹配算法
2. ADL语言 3. 伪代码
function naivePatternMatching(S, P):n length(S) # 目标串的长度m length(P) # 模式串的长度for i from 0 to n - m:j 0while j m and S[i j] P[j]:j j 1if j m: # 如果模式串完全匹配return i # 返回匹配位置return -1 # 未找到匹配# 示例用法
S ABABCABAB
P ABAB
result naivePatternMatching(S, P)
if result ! -1:print(模式串在目标串中的位置:, result)
else:print(未找到匹配)4. C语言实现
#include stdio.h
#include string.hint naivePatternMatching(const char* S, const char* P) {int n strlen(S); // 目标串的长度int m strlen(P); // 模式串的长度for (int i 0; i n - m; i) {int j 0;while (j m S[i j] P[j]) {j;}if (j m) { // 如果模式串完全匹配return i; // 返回匹配位置}}return -1; // 未找到匹配
}int main() {const char* S QomolangmaH;const char* P lang;
// const char* P gan;int result naivePatternMatching(S, P);if (result ! -1) {printf(模式串在目标串中的位置: %d\n, result);} else {printf(未找到匹配\n);}return 0;
}5 时间复杂度 朴素模式匹配算法的优点是过程简单缺点是效率低。在最坏情况下该算法要匹配n-m1次每次匹配要做m次比较因此最坏情况下的比较次数是m×(n-m1)时间复杂性为O(m×(n-m1))通常情况下m的值远小于n的值于是最坏情况下的时间复杂性可粗略地记为O(n×m)。对于长文本和模式串可能会导致性能问题。因此有更高效的模式匹配算法如KMP和Boyer-Moore等用于更快速地找到匹配位置具体内容详见后文。
