文件名称：串匹配算法——kmp算法，并行算法
文件大小：246KB
文件格式：DOC
更新时间：2011-11-11 09:24:13
串匹配 kmp 随机串匹配算法
串匹配（String Matching）问题是计算机科学中的一个基本问题，也是复杂性理论中研究的最广泛的问题之一。它在文字编辑处理、图像处理、文献检索、自然语言识别、生物学等领域有着广泛的应用。而且，串匹配是这些应用中最耗时的核心问题，好的串匹配算法能显著地提高应用的效率。因此，研究并设计快速的串匹配算法具有重要的理论价值和实际意义。 串匹配问题实际上就是一种模式匹配问题，即在给定的文本串中找出与模式串匹配的子串的起始位置。最基本的串匹配问题是关键词匹配（Keyword Matching）。所谓关键词匹配，是指给定一个长为n的文本串T[1，n]和长为m的模式串P[1，m]，找出文本串T中与模式串所有精确匹配的子串的起始位置。串匹配问题包括精确串匹配（Perfect String Matching）、随机串匹配（Randomized String Matching）和近似串匹配（Approximate String Matching）。另外还有多维串匹配（Multidimensional String Matching）和硬件串匹配（Hardware String Matching）等。 本章中分别介绍改进的KMP串匹配算法，采用散列技术的随机串匹配算法，基于过滤算法的近似串匹配算法，以及它们的MPI编程实现。