上海交大计算机系数据结构窦延平讲稿_4_串.ppt

目录 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 4.3.2 KMP算法 * * 物料管理 LILST * * * Data Structures and AlgorithmsStrings 4.1串、存储、串的基本运算  4.1.1 串定义 4.1.2串的存储 4.1.3串的基本操作4.2字符串类4.3串的模式匹配 4.3.1 Brute-Force算法(BF算法) 4.3.2 KMP算法 第 四 章 串 1、串的定长顺序存储表示:采用字符串数组存储字符串，即通常用连续空间保存字符串。 模式 P（样品、子串）：要寻找的字符串， 存于串 pat 之中； 主串：在其中寻找模式的主字符串， 存于字符串 S 之中； #include string.h class String { private: char *str; // 存储String串的数组。 int size; // String串的长度。 public: String ( const String t ); // 从一个已有串t，构造一个新串。 String ( char * const p) { //从一个已有的字符串，创建一个串 String。 String ( ); // 构造一个空串。 ~String ( ){delete [ ]str;}; // 析构函数 char operator[ ](int i); // 带有越界判断的下标运算。 int operator = = ( const String t); // 等于。 int Find( const String t, int start); // 从串中的第start个字符起，向后查找串t第一次在串中出现的位置。 // 找到返回位置序号，未找到返回 –1。 }; 1、串的定长顺序存储表示 String::String (const String t) { //从一个已有串t进行复制，从而构造一个串。 int len=t.size; //求 串长度。 str = new char[len+1]; Exception( !str, Fail to apply an array! ); size = t.size; strcpy (str, t.str); } String::String ( char * const p) { //从一个已有的字符串，创建一个串 String。 int len=0; //求串长度。 char * q = p; while( *q++ != ‘\0’) len++; str = new char[len+1]; size = len; strcpy (str, p ); } String::String ( ) { // 创建一个空串。 str = new char[1]; // 仅有一个单元的字符串数组。 Exception( !str, Fail to apply an array! ); size = 0; str[0] = ‘\0’; // 仅有结束符，为空串 } 1、串的定长顺序存储表示 模式 P（样品、子串）：要寻找的字符串， 存于串 pat 之中； 主串：在其中寻找模式的主字符串， 存于字符串 S 之中 问题：在主串中寻找一个模式？如何做，更快？ 采用最笨的办法，一旦发现出现字符不匹配，则整个模式相对于原来的位置右移一位。 如下图所示： ……Si-j Si-j+1 …… Si-1 Si Si+1…… P0 P1 …… Pj-1Pj …… … 失配位置 P0 P1 …… Pj-1 Pj …… 下次匹配位置 e.g: S=a b c a b c a b c d P= a b c a b c d a b c a b c d 模式右移一位 1、串的定长顺序存储表示 模式 P（样品、子串）：要寻找的字符串， 存于串 pat 之中； 主串：在其中寻找模式的主字符串， 存于字符串 S 之中 问题：在主串中寻找一个模式？如何