下载文档原格式
java dfa算法与实现Java DFA算法与实现引言：有限状态自动机（DFA）是一种用于识别和处理模式匹配的算法。
在计算机科学领域，DFA被广泛应用于字符串匹配、编译器设计、自然语言处理等领域。
本文将介绍DFA算法的原理以及如何使用Java 语言实现一个简单的DFA。
一、DFA算法原理：DFA算法是基于状态转换的自动机模型，它由五个元素组成：输入字母表、状态集合、初始状态、接受状态集合和状态转换函数。
DFA 算法的核心思想是根据输入字母表逐个读取输入字符，并根据状态转换函数将当前状态转换为下一个状态，直到达到接受状态或者无法进行状态转换为止。
二、DFA算法实现步骤：1. 定义输入字母表：根据具体需求定义合适的输入字母表，例如只包含小写字母。
2. 定义状态集合：根据问题的需求定义状态集合，例如对于一个简单的字符串匹配问题，可以定义状态集合为{0, 1}，其中0表示未匹配，1表示已匹配。
3. 定义初始状态和接受状态集合：根据实际需求定义初始状态和接受状态集合，例如初始状态为0，接受状态集合为{1}，表示只有当状态为1时才算匹配成功。
4. 定义状态转换函数：根据输入字母表和状态集合定义状态转换函数，例如对于输入字母表中的字符c，如果当前状态为0且c为目标字符串中的字符，则将状态转换为1，否则保持状态为0。
5. 实现DFA算法：根据上述定义的输入字母表、状态集合、初始状态、接受状态集合和状态转换函数，使用循环结构逐个读取输入字符串中的字符，并根据状态转换函数更新当前状态，直到达到接受状态或者无法进行状态转换。
三、Java实现DFA算法示例：下面是一个简单的Java代码示例，实现了一个DFA算法用于判断输入字符串是否包含目标字符串。
```javapublic class DFAAlgorithm {private static final int[][] TRANSITION_TABLE = {{1, 0}, // 当前状态为0，输入字符为目标字符串中的字符时，转换到状态1，否则保持状态为0{1, 1} // 当前状态为1，输入字符为目标字符串中的字符时，保持状态为1，否则保持状态为1};private static final int INITIAL_STATE = 0;private static final int ACCEPT_STATE = 1;public static boolean containsTargetString(String input, String target) {int currentState = INITIAL_STATE;for (char c : input.toCharArray()) {int inputIndex = target.indexOf(c);if (inputIndex == -1) {currentState = TRANSITION_TABLE[currentState][0];} else {currentState = TRANSITION_TABLE[currentState][1];}}return currentState == ACCEPT_STATE;}public static void main(String[] args) {String input = "Hello, world!";String target = "world";if (containsTargetString(input, target)) {System.out.println("Input string contains target string.");} else {System.out.println("Input string does not contain target string.");}}}```以上代码中，TRANSITION_TABLE是状态转换表，其中第一行表示当前状态为0时的转换情况，第二行表示当前状态为1时的转换情况。
模式匹配算法及应用教案模式匹配算法是指在一个文本字符串中查找一个给定的模式（也称为目标字符串）的算法。
在计算机科学中，模式匹配是一个非常重要的问题，在许多应用领域都有广泛的应用，如字符串匹配、数据压缩、图像处理等。
一、模式匹配算法的分类1. 朴素模式匹配算法：朴素模式匹配算法（也称为暴力算法）是一种简单直观的模式匹配算法。
它的基本思想是从目标字符串的第一个字符开始，对比目标字符串和模式字符串的每个字符是否相等，如果不等，则向右移动目标字符串一个位置，再次开始对比；如果相等，则继续对比下一个字符，直到模式字符串的所有字符都匹配成功或目标字符串结束。
朴素模式匹配算法的时间复杂度为O(mn)，其中m是目标字符串的长度，n 是模式字符串的长度。
2. KMP算法：KMP算法是一种高效的模式匹配算法，它的核心思想是通过利用已匹配部分的信息来避免不必要的对比。
具体来说，KMP算法通过构建一个"部分匹配表"（也称为next数组），来记录模式字符串中每个字符前面的最长匹配前缀和后缀的长度。
在匹配过程中，当出现不匹配的字符时，可以利用部分匹配表的信息来确定下一次对比的位置，从而实现跳跃式的移动。
KMP算法的时间复杂度为O(m+n)，其中m是目标字符串的长度，n是模式字符串的长度。
3. Boyer-Moore算法：Boyer-Moore算法是一种基于字符比较的模式匹配算法，它的主要思想是从目标字符串的最末尾开始比较。
通过预先计算模式字符串中的每个字符在模式字符串中最右出现的位置，可以根据目标字符串中不匹配的字符在模式字符串中的位置进行跳跃移动，从而实现快速的匹配。
Boyer-Moore算法的时间复杂度平均情况下为O(n/m)，其中n是目标字符串的长度，m是模式字符串的长度。
二、模式匹配算法的应用1. 字符串匹配：字符串匹配是模式匹配算法的最常见应用之一。
在很多应用中，需要在一个文本字符串中查找给定的子字符串。
模式匹配算法的研究与实现作者：李萍赵润林来源：《电脑知识与技术》2017年第18期摘要：模式匹配是字符串的基本运算之一，也是数据结构课程的重点算法之一。
在当今文本信息海量增长的时代，如何快速地定位就显得尤为重要。
该文通过朴素模式匹配算法与KMP算法的比较说明各自的优缺点，同时通过提高获取next数组的效率，加快KMP算法的匹配速率。
关键词：模式匹配；KMP；NEXT函数；文本搜索中图分类号：TP391 文献标识码：A 文章编号：1009-3044（2017）18-0025-02从计算机诞生至今，文本信息海量地增长，无论是在金融、航海、DNA检测、网络入侵等领域都需要在文本中快速地查找所需要的信息，因此设计出一个好模式匹配算法，不公可以高效地进行定位，还可以提高文本编辑能力，提高改善人类的生活。
模式匹配即子串的定位操作，是数据结构中逻辑结构为串的最重要操作之一。
该算法的主要目的是找出特定的模式串在一个较长的字符串中出现的位置。
如有两个字符串T称为模式串，字符串s称为主串，找出模式T在主S中的首次出现的位置。
一旦模式T在目标s中找到，就称发生一次匹配。
例如，目标串S=’ababeabcaebab’，模式串T=’abcac’，则匹配结果为6，其中经典的模式匹配算法包括朴素匹配算法、KMP。
1朴素模式匹配算法朴素模式匹配算法的基本思想是在模式串T和主串S中，使用循环变量I，j，分别在模式串和主串中循环跑动，如果模式串与主串对应字符相等S[i]=T[j]，则同时后移；如果模式串与主串对应字符不相等S[i]≠[j]，则模式串回滚到起始位置，而主串回滚到起始位置的下一个字符。
如此一直循环直至主串结束或模式串结束。
朴素模式匹配算法的回溯演示如下：算法流程图描述如下：2 KMP算法与朴素模式匹配算法比较，KMP算法最大的特点是模式串在匹配不相等的情况下，不再回溯，而是匹配串进行滑动，所以匹配串滑动的位置是算法的关键。
串的模式匹配算法在串的模式匹配算法中，最著名的算法包括暴力法、KMP算法、Boyer-Moore算法及其改进算法（Bad Character Rule和Good Suffix Rule）等。
下面将对这些算法进行详细介绍。
1. 暴力法（Brute Force）：暴力法是最简单的模式匹配算法，其基本思想是从文本串的第一个字符开始与模式串逐个比较，如存在字符不匹配，则在文本串中向后移动一位重新开始匹配，直到找到匹配的位置或者遍历完整个文本串。
暴力法的时间复杂度为O(mn)，其中m和n分别为文本串和模式串的长度。
2. KMP算法（Knuth-Morris-Pratt Algorithm）：KMP算法是一种高效的模式匹配算法，利用已匹配的字符信息来避免不必要的匹配比较。
算法的核心思想是通过预处理模式串构建一个next数组（或称为部分匹配表），记录模式串中能够跳过的位置。
当出现字符不匹配时，根据next数组中的值来决定模式串的移动位置。
KMP算法的时间复杂度为O(m+n)，其中m和n分别为文本串和模式串的长度。
3. Boyer-Moore算法：Boyer-Moore算法是一种基于“坏字符规则”（Bad Character Rule）和“好后缀规则”（Good Suffix Rule）的模式匹配算法。
坏字符规则指的是在字符串匹配过程中，若出现不匹配情况，则将模式串向右移动，直到模式串中的字符与坏字符对齐。
而好后缀规则则是根据好后缀在模式串中出现的位置来进行移动。
Boyer-Moore算法的时间复杂度为O(mn)，但在实际应用中，其平均性能往往优于KMP算法。
4. 改进的Boyer-Moore算法：改进的Boyer-Moore算法对原始的Boyer-Moore算法进行了优化，提出了“坏字符规则”的改进和“好后缀规则”的改进。
其中，“坏字符规则”的改进包括“坏字符数组”（Bad Character Array）和“好后缀规则”的改进包括“好后缀数组”（Good Suffix Array）。
多模式串匹配算法随着互联网和大数据时代的到来，数据量的急速增长使得文本处理和文本搜索算法越来越受到关注。
而多模式串匹配算法（Multiple Pattern String Matching）就是一个十分重要的文本处理算法，它能够高效地在文本中匹配多个模式串，被广泛应用于信息检索、网络安全等领域。
本文将介绍多模式串匹配算法的基本概念、实现方法和应用场景。
一、基本概念在介绍多模式串匹配算法之前，我们需要先了解下面几个概念：1. 模式串（Pattern String）：需要在文本中匹配的字符串。
2. 文本串（Text String）：需要进行匹配的文本。
3. 匹配（Match）：在文本中找到了与模式串相同的字符串。
4. 多模式串（Multiple Pattern）：需要匹配的模式串的集合。
二、实现方法多模式串匹配算法的实现方法有很多种，例如：1. Trie树（字典树）：将多个模式串构建成Trie树，然后在文本中逐个字符匹配，直到匹配到叶子节点为止。
2. AC自动机（Aho-Corasick Algorithm）：AC自动机是一种基于Trie树的改进算法，它可以在Trie树上同时匹配多个模式串，并且具有快速匹配的特点。
3. 后缀数组（Suffix Array）：后缀数组是将一个字符串的所有后缀按字典序排序后得到的数组，利用后缀数组可以高效地搜索模式串。
4. KMP算法（Knuth-Morris-Pratt Algorithm）：KMP算法是一种字符串匹配算法，可以在O(n)的时间复杂度内匹配单个模式串，将其与Trie树等算法结合可以实现多模式串匹配。
三、应用场景多模式串匹配算法在信息检索、网络安全、自然语言处理等领域都有广泛的应用，例如：1. 搜索引擎：搜索引擎需要对用户输入的查询串进行匹配，多模式串匹配算法可以高效地完成这个任务。
2. 病毒检测：病毒检测需要对文件进行扫描，多模式串匹配算法可以快速地检测出是否存在病毒。
串的两种模式匹配算法 模式匹配(模范匹配)：⼦串在主串中的定位称为模式匹配或串匹配(字符串匹配) 。
模式匹配成功是指在主串S中能够找到模式串T，否则，称模式串T在主串S中不存在。
以下介绍两种常见的模式匹配算法：1. Brute-Force模式匹配算法暴风算法，⼜称暴⼒算法。
算法的核⼼思想如下： 设S为⽬标串，T为模式串，且不妨设： S=“s0s1s2…sn-1” ， T=“t0t1t2 …tm-1” 串的匹配实际上是对合法的位置0≦i≦n-m依次将⽬标串中的⼦串s[i…i+m-1]和模式串t[0…m-1]进⾏⽐较：若s[i…i+m-1]=t[0…m-1]：则称从位置i开始的匹配成功，亦称模式t在⽬标s中出现；若s[i…i+m-1]≠t[0…m-1]：从i开始的匹配失败。
位置i称为位移，当s[i…i+m-1]=t[0…m-1]时，i称为有效位移；当s[i…i+m-1] ≠t[0…m-1]时，i称为⽆效位移。
算法实现如下： （笔者偷懒，⽤C#实现，实际上C# String类型已经封装实现了该功能）1public static Int32 IndexOf(String parentStr, String childStr)2 {3 Int32 result = -1;4try5 {6if (parentStr.Length > 1 && childStr.Length > 1)7 {8 Int32 i = 0;9 Int32 j = 0;10while (i < parentStr.Length && j < childStr.Length)11 {12if (parentStr[i] == childStr[j])13 {14 i++;15 j++;16 }17else18 {19 i = i - j + 1;20 j = 0;21 }22 }23if (i < parentStr.Length)24 {25 result = i - j;26 }27 }28 }29catch (Exception)30 {31 result = -1;32 }33return result;34 } 该算法的时间复杂度为O(n*m) ，其中n 、m分别是主串和模式串的长度。
BF算法，也就是Brute Force算法，是一种基本的字符串模式匹配算法。
它通过遍历文本串，逐一比较字符来实现模式匹配。
以下是BF算法的800字说明：1. 算法原理BF算法的基本原理是在文本串中从左到右依次扫描，对于扫描到的每一个位置，将该位置的文本与模式串中的每个模式字符进行比较，以确定是否存在匹配。
如果找到了匹配，则算法结束；否则，继续扫描下一个位置。
2. 算法步骤（1）初始化两个指针，一个指向文本串的起始位置，另一个指向模式串的起始位置；（2）比较起始位置的字符是否匹配，如果不匹配则算法结束；（3）如果匹配，移动两个指针，分别到下一个位置继续比较；（4）重复步骤（2）和（3），直到文本串完全扫描完或者没有匹配到为止。
3. 算法时间复杂度BF算法的时间复杂度是O(n*m)，其中n是文本串的长度，m是模式串的长度。
这是因为每次比较都需要花费一定的时间，而整个过程需要比较n-m+1次。
4. 算法优缺点优点：简单易懂，实现起来相对容易。
缺点：时间复杂度较高，对于较长的文本串和模式串，效率较低。
此外，BF算法只能用于查找单一的模式，对于多个模式的查找需要使用其他算法。
5. 实际应用BF算法在实际应用中主要用于文本搜索、模式匹配等场景。
例如，在搜索引擎中，BF算法常被用于网页的关键词匹配和搜索结果排序。
此外，BF算法还可以用于病毒扫描、文件校验等领域。
总之，BF算法是一种基本的字符串模式匹配算法，适用于简单的文本搜索和模式匹配场景。
虽然其时间复杂度较高，但对于一些特定的应用场景，BF算法仍然是一种有效的方法。
当然，随着计算机技术的发展，还有很多高效的模式匹配算法被提出，如KMP算法、BM算法、Rabin-Karp算法等，可以根据具体应用场景选择合适的算法。
实现顺序串的各种模式匹配算法序号一：引言实现顺序串的各种模式匹配算法是一项重要而复杂的任务。
在计算机科学领域，这一问题一直备受关注，因为它涉及到如何高效地在一个文本中找到一个模式的出现。
通过使用不同的算法和数据结构，我们可以在实际应用中更有效地实现字符串匹配。
在本文中，我们将深入探讨各种模式匹配算法，包括它们的原理、优缺点以及适用场景，以便读者能够更全面地理解和应用这些算法。
序号二：模式匹配算法的基本原理在开始讨论不同的模式匹配算法之前，让我们先了解一下模式匹配的基本原理。
模式匹配是指在一个文本串中查找一个模式串的过程。
具体来说，我们需要在文本串中以每一个位置为起点，依次比较模式串和文本串的对应字符，从而确定模式串是否出现在文本串中。
这个过程类似于在一本书中找到特定章节的名字，只不过在计算机中我们需要以更快的速度完成这一任务。
序号三：常见的模式匹配算法及其优缺点在实际应用中，有许多不同的模式匹配算法可供选择。
其中，最常见的包括朴素匹配算法、KMP算法、Boyer-Moore算法、Rabin-Karp 算法等。
每种算法都有其独特的优缺点，以适应不同的应用场景。
朴素匹配算法是一种简单直观的算法，它从文本串的每一个位置开始和模式串进行匹配，直到找到匹配或者遍历完整个文本串为止。
这种算法的优点是实现简单，但是对于大规模文本串和模式串来说效率较低。
KMP算法是一种高效的模式匹配算法，它利用了模式串自身的特点来快速匹配文本串。
通过构建部分匹配表，KMP算法可以在匹配过程中跳过一些已经匹配过的位置，从而提高匹配的效率。
其主要缺点是需要额外的空间来存储部分匹配表，因此在内存有限的场景下可能不适用。
Boyer-Moore算法是另一种经典的模式匹配算法，它通过利用模式串和文本串之间的信息来跳过一些不可能匹配的位置，从而减少比较次数。
这使得Boyer-Moore算法在最坏情况下的时间复杂度较低，适用于大规模文本串和模式串的匹配。
数据结构—串的模式匹配数据结构—串的模式匹配1.介绍串的模式匹配是计算机科学中的一个重要问题，用于在一个较长的字符串（称为主串）中查找一个较短的字符串（称为模式串）出现的位置。
本文档将详细介绍串的模式匹配算法及其实现。
2.算法一：暴力匹配法暴力匹配法是最简单直观的一种模式匹配算法，它通过逐个比较主串和模式串的字符进行匹配。
具体步骤如下：1.从主串的第一个字符开始，逐个比较主串和模式串的字符。
2.如果当前字符匹配成功，则比较下一个字符，直到模式串结束或出现不匹配的字符。
3.如果匹配成功，返回当前字符在主串中的位置，否则继续从主串的下一个位置开始匹配。
3.算法二：KMP匹配算法KMP匹配算法是一种改进的模式匹配算法，它通过构建一个部分匹配表来减少不必要的比较次数。
具体步骤如下：1.构建模式串的部分匹配表，即找出模式串中每个字符对应的最长公共前后缀长度。
2.从主串的第一个字符开始，逐个比较主串和模式串的字符。
3.如果当前字符匹配成功，则继续比较下一个字符。
4.如果当前字符不匹配，则根据部分匹配表的值调整模式串的位置，直到模式串移动到合适的位置。
4.算法三：Boyer-Moore匹配算法Boyer-Moore匹配算法是一种高效的模式匹配算法，它通过利用模式串中的字符出现位置和不匹配字符进行跳跃式的匹配。
具体步骤如下：1.构建一个坏字符规则表，记录模式串中每个字符出现的最后一个位置。
2.从主串的第一个字符开始，逐个比较主串和模式串的字符。
3.如果当前字符匹配成功，则继续比较下一个字符。
4.如果当前字符不匹配，则根据坏字符规则表的值调整模式串的位置，使模式串向后滑动。
5.算法四：Rabin-Karp匹配算法Rabin-Karp匹配算法是一种基于哈希算法的模式匹配算法，它通过计算主串和模式串的哈希值进行匹配。
具体步骤如下：1.计算模式串的哈希值。
2.从主串的第一个字符开始，逐个计算主串中与模式串长度相同的子串的哈希值。
C语言中的模式匹配算法在计算机科学中，模式匹配是一种非常重要的算法，它可以用于文本匹配、字符串匹配、图形识别等领域。
在C语言中，有多种模式匹配算法可以用于实现字符串匹配操作。
本文将介绍C语言中的一些常用模式匹配算法，包括Brute-Force算法、Knuth-Morris-Pratt(KMP)算法和Boyer-Moore算法。
一、Brute-Force算法Brute-Force算法，也称为朴素模式匹配算法，是最简单直接的一种算法。
它的思想是从目标字符串的第一个字符开始，依次和模式字符串对应位置的字符比较，如果出现不匹配的字符，则将目标字符串的指针向后移动一位，再次进行比较，直到找到匹配的子串或遍历完整个目标字符串。
Brute-Force算法的时间复杂度为O(m*n)，其中m为目标字符串的长度，n为模式字符串的长度。
该算法简单易懂，但对于较长的字符串匹配操作效率较低。
二、Knuth-Morris-Pratt(KMP)算法KMP算法是一种优化的字符串模式匹配算法，它利用了模式字符串中的信息来避免不必要的比较。
该算法的核心思想是，当模式字符串中的某一部分与目标字符串不匹配时，不需要将目标字符串的指针回溯到上一次比较的位置，而是利用已有的信息直接跳过一部分字符，从而提高了匹配的效率。
KMP算法的时间复杂度为O(m+n)，其中m为目标字符串的长度，n为模式字符串的长度。
相较于Brute-Force算法，KMP算法在处理较长字符串时能够明显提高匹配速度。
三、Boyer-Moore算法Boyer-Moore算法是一种更加高效的字符串模式匹配算法，它充分利用了模式字符串中的信息进行跳跃式匹配。
该算法的核心思想包括两个关键步骤：坏字符规则和好后缀规则。
坏字符规则是通过将模式串与目标串在不匹配的位置对齐，找出目标串中不匹配的字符在模式串中最后一次出现的位置，从而跳过一部分字符的比较。
好后缀规则则是利用模式串与目标串中已匹配的部分，找出能够与好后缀匹配的最长子串，直接将模式串向后滑动到该子串的位置，从而跳过一部分字符的比较。
一、实验目的本次实验旨在让学生熟悉并掌握模式匹配的基本概念、算法及其应用。
通过实验，学生能够了解模式匹配算法的原理，掌握几种常见的模式匹配算法（如KMP算法、BF算法等）的实现方法，并能够运用这些算法解决实际问题。
二、实验环境1. 操作系统：Windows 102. 编程语言：C++3. 开发环境：Visual Studio 2019三、实验内容1. 模式匹配基本概念- 模式匹配：在给定的文本中查找一个特定模式的过程。
- 模式：要查找的字符串。
- 文本：包含可能包含模式的字符串。
2. KMP算法- KMP算法（Knuth-Morris-Pratt）是一种高效的字符串匹配算法，其核心思想是避免重复比较已经确定不匹配的字符。
- 实现步骤：1. 构造一个部分匹配表（next数组）。
2. 遍历文本和模式，比较字符，并使用next数组调整模式的位置。
3. BF算法- BF算法（Boyer-Moore）是一种高效的字符串匹配算法，其核心思想是利用坏字符规则和好后缀规则来减少不必要的比较。
- 实现步骤：1. 计算坏字符规则。
2. 计算好后缀规则。
3. 遍历文本和模式，比较字符，并使用坏字符规则和好后缀规则调整模式的位置。
4. 模式匹配算法比较- 比较KMP算法和BF算法的时间复杂度、空间复杂度及适用场景。
四、实验步骤1. 初始化- 定义文本和模式字符串。
- 初始化模式匹配算法的参数。
2. 构造next数组（KMP算法）- 根据模式字符串构造部分匹配表（next数组）。
3. 计算坏字符规则和好后缀规则（BF算法）- 根据模式字符串计算坏字符规则和好后缀规则。
4. 遍历文本和模式- 使用KMP算法或BF算法遍历文本和模式，比较字符，并调整模式的位置。
5. 输出结果- 输出匹配结果，包括匹配的位置和匹配次数。
五、实验结果与分析1. KMP算法- 时间复杂度：O(nm)，其中n为文本长度，m为模式长度。
- 空间复杂度：O(m)。
五、详细设计
#include<string>
#include<fstream>
#include<cstdlib>
#include<time.h>
using namespace std;
#define MAX 100000
#define M 69
class String
{
private:
int n;
char *str;
int *count; //记录子串在主串中出现的位置
int Find(int i,String &P); // 简单匹配算法找到最近的匹配串后立即停止，而不向下继续且缺乏一个数组记录位置
int *f ; //记录失败函数
void Fail();
int KMPFind(int i,String &P); //改进的失败函数
void ImproveFail();
int KMPFindImprove(int i,String &P);
public:
String(); //建立一个空串
String(const char *p);
String(const String &p); //拷贝函数
~String();
int Length() {return n;}; //返回当前串对象长度
void Output() {cout<<str;}; //输出字符串
int Find(String &P); //简单匹配算法
int KMPFind(String &P); //KMP匹配算法
int KMPFindImprove(String &P); //改进的KMP匹配算法
void Output2(); //输出子串在主串中出现的位置
};
int String::KMPFindImprove(String &P)
{
int sum=0;
int j=KMPFindImprove(0,P);
while(j!=-1)
{
count[sum++]=j;
if(j<=n-P.n) j=KMPFindImprove(j+P.n,P);
}
return sum;
}
void String::Output2() //输出子串在主串中的位置
{
int i=0;
while(count[i]!=count[i+1] && i<MAX-1) //若不再有新的子串匹配，则count[i]与count[i+1]均为0
{
cout<<count[i]<<" ";
i++;
}
}
void menu()
{
cout<<"********************************************"<<endl;
cout<<endl;
cout<<endl;
cout<<" 1.简单模式匹配算法"<<endl;
cout<<endl;
cout<<endl;
cout<<" 2.KMP模式匹配算法"<<endl;
cout<<endl;
cout<<" 4.退出"<<endl;
cout<<endl;
cout<<endl;
cout<<"################################################"<<endl;
}
void main()
{
int choice=0;
menu();
clock_t start,finish;
while(choice!=4)//循环可以连续选择
{
cout<<"请输入选择"<<endl;
cin>>choice;
if(choice==1)
{
String s1("Through aretro spectivelook at the mathe matics teaching at USTC, this article summarizes university's teaching achievements in past 45 years.");
s1.Output();
cout<<endl;
String s2("teaching");
start=clock();
int m=s1.Find(s2);
s2.Output();
cout<<"出现的次数为:"<<m<<endl;
if(m!=0)
{
cout<<"匹配的位置是";
s1.Output2();
cout<<endl;
}
finish=clock();
cout<<endl<<"time is:"<<(double)(finish-start)/CLK_TCK<<endl;
}
if(choice==2)
{
clock_t start,finish;
start=clock();
String s1("Through a retrospective look at the mathematics teaching at USTC, this article summarizes university's teaching achievements in past 45 years.");
s1.Output(); cout<<endl;
String s2("teaching");
s2.Output(); cout<<endl;
int n=s1.KMPFind(s2);
cout<<"出现的次数为:"<<n<<endl;
if(n!=0)
{
cout<<n<<"匹配的位置是";
s1.Output2();
cout<<endl;
}
finish=clock();
cout<<endl<<"time is:"<<(double)(finish-start)/CLK_TCK<<endl;
}
if(choice==3)
{
clock_t start,finish;
start=clock();
String s1("Through a retrospective look at the mathematics teaching at USTC, this article summarizes university's teaching achievements in past 45 years.");
s1.Output(); cout<<endl;
String s2("teaching");
s2.Output(); cout<<endl;
int n=s1.KMPFindImprove(s2);
cout<<"出现在主串中的次数为:"<<n<<endl;
if(n!=0)
{
cout<<n<<"匹配的位置是";
s1.Output2();
cout<<endl;
}
finish=clock();
cout<<endl<<"time is:"<<(double)(finish-start)/CLK_TCK<<endl;
}
}
}。
