当前位置：首页 > news >正文

字符串算法

news 来源：原创 2024/9/20 0:45:19

1. 引言

2. 基础概念

3. 字符串匹配算法

朴素匹配算法

KMP（Knuth-Morris-Pratt）算法

Boyer-Moore算法

1. 引言

简述字符串算法的重要性 字符串是计算机科学中的基本数据结构，广泛应用于文本处理、数据分析、网络安全等领域。有效的字符串算法可以极大地提高这些应用的效率和性能，因此对这些算法的理解和掌握至关重要。

常见的字符串处理任务

匹配：查找一个字符串是否存在于另一个字符串中。
搜索：在大量字符串中快速找到目标字符串。
排序：根据字典序或其他规则对字符串数组进行排序。
压缩：减少字符串的存储空间。

2. 基础概念

字符串的定义与表示 字符串是由字符组成的有限序列，通常用于表示文本数据。字符串可以用不同的编码方式进行存储和处理，如ASCII和Unicode。

ASCII码与Unicode

ASCII码：采用7位或8位二进制编码，用于表示英文字符及常用符号。
Unicode：一种通用的字符编码标准，可以表示几乎所有语言的字符，常用的编码方式包括UTF-8、UTF-16等。

字符串的基本操作

连接：将两个或多个字符串拼接成一个新字符串。
截取：从字符串中提取一个子字符串。
查找：寻找某个子字符串在字符串中的位置。
替换：将字符串中的某个子字符串替换为另一个字符串。

3. 字符串匹配算法

朴素匹配算法

算法原理

朴素匹配算法（Naive String Matching Algorithm）是一种最简单的字符串匹配算法，其核心思想是逐个字符地比较目标字符串（Text）中的每一个子串与模式字符串（Pattern），直到找到匹配的子串或遍历完整个目标字符串。

算法步骤

将目标字符串的第一个字符与模式字符串的第一个字符进行比较。
如果匹配，继续比较下一个字符；如果不匹配，从目标字符串的下一个字符开始重新比较。
重复上述步骤，直到找到匹配或遍历完整个目标字符串。

代码示例

python语言：

def naive_string_matcher(text, pattern):n = len(text)m = len(pattern)for i in range(n - m + 1):match = Truefor j in range(m):if text[i + j] != pattern[j]:match = Falsebreakif match:print(f"Pattern found at index {i}")# 示例使用
text = "ABCDEFABCDEF"
pattern = "CDE"
naive_string_matcher(text, pattern)

C语言：

# include <stdio.h>
# include <stdlib.h>typedef struct String {char *data;int len;
}String;String *initString(){String *s = (String *)malloc(sizeof(String));s->data = NULL;s->len = 0;return s;
}void stringAssign(String *s, char *data){// 释放字符串结构体中的数据内存if (s -> data) {free(s -> data);}int len = 0;// 将指针 data 的值赋给指针 temp，使得 temp 指向 data 所指向的内存地址。char* temp = data;// 通过遍历字符串中的每个字符，直到遇到字符串结束符'\0'，//每遍历一个字符，长度计数器len就增加1。while (*temp) {len++;temp++;}if (len == 0){s -> data = NULL;s -> len = 0;}else{temp = data;s -> len = len;s -> data = (char *)malloc((len + 1) * sizeof(char));for (int i = 0; i <= len; i++,temp++){s -> data[i] = *temp;}}
}void printString(String *s){// 打印字符串的函数，接受一个指向String结构体的指针作为参数// 遍历字符串中的每个字符，使用箭头连接并打印出来for (int i = 0; i < s -> len; i++){printf(i == 0 ? "%c " : "-> %c", s -> data[i]);}printf("\n");
}void forceMatch(String *master, String *sub){// 字符串匹配的暴算法，接受两个指向String结构体的指针作为参数int i = 0,j = 0;while (i < master -> len && j < sub -> len){    if (master -> data[i] == sub -> data[j]){i++;j++;}else{// 匹配失败，重置i(回到起点的下一位)，j，继续匹配i = i - j + 1;j = 0;}}if (j == sub -> len){printf("force Match success!\n");}else{printf("force Match fail!\n");}
}int main(){String *s1 = initString();String *s2 = initString();stringAssign(s1, "hello world");stringAssign(s2, "world");printString(s1);printString(s2);forceMatch(s1, s2);return 0;
}

输出结果

Pattern found at index 2
Pattern found at index 8

时间复杂度分析 朴素匹配算法的时间复杂度取决于目标字符串的长度 n 和模式字符串的长度 m：

最坏情况：O((n - m + 1) * m)，即在每个位置都进行完全比较。
最优情况：O(n)，即模式字符串在目标字符串的开头找到。

案例分析 考虑一个实际应用场景，比如在一个长文章中搜索某个特定的词语。在这样的场景下，朴素匹配算法虽然简单，但在大多数情况下效率较低，尤其是当目标字符串和模式字符串都很长时。

图解说明 可以通过图示展示朴素匹配算法的逐步匹配过程。在下图中，每行代表一次新的比较，绿色表示成功匹配的字符，红色表示匹配失败后重新开始。

总结朴素匹配算法虽然易于理解和实现，但在处理大型数据集时性能不佳。因此，通常会使用更为复杂和高效的算法，如KMP算法或Boyer-Moore算法。

KMP（Knuth-Morris-Pratt）算法

算法背景与概述 KMP算法是由Donald Knuth、Vaughan Pratt和James H. Morris在1977年提出的一种字符串匹配算法。KMP算法通过预处理模式字符串来避免在匹配过程中对目标字符串的字符进行重复比较，从而提高匹配效率。

部分匹配表（前缀表）的构建 KMP算法的核心在于部分匹配表（又称为前缀表）的构建。该表用于记录模式字符串中每个位置的最长相同前缀与后缀的长度，从而在模式字符串出现部分匹配时，能够快速跳转至下一个可能匹配的位置。

构建步骤

初始化前缀表，长度为模式字符串的长度。
遍历模式字符串，对于每个位置计算最长相同前缀与后缀的长度，并存入前缀表中。

代码示例：前缀表构建

def build_prefix_table(pattern):m = len(pattern)prefix_table = [0] * mj = 0  # length of the previous longest prefix suffixi = 1while i < m:if pattern[i] == pattern[j]:j += 1prefix_table[i] = ji += 1else:if j != 0:j = prefix_table[j - 1]else:prefix_table[i] = 0i += 1return prefix_table# 示例使用
pattern = "ABABCABAB"
prefix_table = build_prefix_table(pattern)
print("Prefix Table:", prefix_table)

输出结果

Prefix Table: [0, 0, 1, 2, 0, 1, 2, 3, 2]

算法步骤

使用前缀表进行模式匹配，比较目标字符串与模式字符串。
当出现部分匹配时，利用前缀表跳过一些无用的比较。
重复上述过程，直到找到匹配或遍历完整个目标字符串。

代码示例：KMP算法

python语言：

def KMP_search(text, pattern):n = len(text)m = len(pattern)prefix_table = build_prefix_table(pattern)i = 0  # index for textj = 0  # index for patternwhile i < n:if pattern[j] == text[i]:i += 1j += 1if j == m:print(f"Pattern found at index {i - j}")j = prefix_table[j - 1]elif i < n and pattern[j] != text[i]:if j != 0:j = prefix_table[j - 1]else:i += 1# 示例使用
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
KMP_search(text, pattern)

C语言：

#include <stdio.h>
#include <stdlib.h>typedef struct String
{char *data;int len;
} String;String *initString()
{String *s = (String *)malloc(sizeof(String));s->data = NULL;s->len = 0;return s;
}void stringAssign(String *s, char *data)
{if (s->data){free(s->data);}int len = 0;char *temp = data;while (*temp){len++;temp++;}if (len == 0){s->data = NULL;s->len = 0;}else{temp = data;s->len = len;s->data = (char *)malloc(sizeof(char) * (len + 1));for (int i = 0; i < len; i++){s->data[i] = *temp;temp++;}}
}void printString(String *s)
{if (s->data){for (int i = 0; i < s->len; i++){printf(i == 0 ? "%c" : "-> %c", s->data[i]);}}printf("\n");
}int *getNext(String *s)
{int *next = (int *)malloc(sizeof(int) * s->len);int i = 0, j = -1;next[0] = -1;while (i < s->len - 1){if (j == -1 || s->data[i] == s->data[j]){i++;j++;next[i] = j;}else{j = next[j];}}return next;
}void printNext(int *next, int len)
{for (int i = 0; i < len; i++){printf(i == 0 ? "%d" : "-> %d", next[i]);}printf("\n");
}void kmpMatch(String *master, String *sub, int* next){// 函数kmpMatch用于实现KMP字符串匹配算法// 参数master: 主字符串// 参数sub: 子字符串// 参数next: next数组，用于存储子字符串的最长公共前后缀长度int i = 0,j = 0;while (i < master->len && j < sub->len){if (j == -1 || master -> data[i] == sub -> data[j]){i++;j++;}else {j = next[j];}}if (j == sub->len){printf(" kmp match success. \n");}else{printf("kmp match fail. \n");}
}      int main()
{String *s1 = initString();String *s2 = initString();stringAssign(s1, "hello world");stringAssign(s2, "world");printString(s1);int *next = getNext(s2);printNext(next, s2->len);kmpMatch(s1, s2, next);return 0;
}

输出结果