第四章字符串修改

第四章字符串 计算机学科中，字符串在诸如文本处理、生物计算中的DNA信息的提取等非数值应用中有非常广泛的作用。字符串是特殊的线性表，其特殊在元素受限（只允许字符作为元素），所以也称它们为元素受限的线性表。字符串（String）概念字符串是组成元素（结点）为字符的线性表，简称“串”。记作：s=“a0a1…an-1"字符串包含的字符个数称为串长。字符串（String）概念假设s1、s2两个字符串，其中s1=a0a1…an-1，s2=b0b1…bm-1，0≤m≤n，如果存在整数i(0≤i≤n-m)，使得对任意j=0,1,…,m-1，都有bj=ai+j同时成立，则称字符串s2是字符串s1的子串，或称包含。字符串（String）概念长度为零的串称为空串，不包含任何字符。注意：区分空串和空白串 空串不包括任何字符，空白串包括空格符等不可见字符。空串是任何字符串的子串，任何串都是其自身的子串。字符串（String）字符串与一般线性表相比特殊在：字符串的数据对象（元素）约束为字符集中的字符；主要的字符集有ASCII和UNICODE一般线性表的基本操作大多以“单个元素”为操作对象，而字符串的基本操作通常以“串整体”为操作对象。字符串逻辑定义字符串的数据元素及其关系元素——任意合法字符类型的数据；关系——唯一前驱唯一后继；字符串的操作在字符串的尾端添加字符、串连接、串复制、串比较、在串中搜索给定的字符或子串。//字符串抽象类定义template<classT>classString{ public: intlength(); boolisEmpty();

voidclear(); stringappend(constcharc); stringconcatenate(constchar*s);

stringcopy(constchar*s);

stringinsert(constcharc,constintindex);

stringfind(constcharc,constintstart);

stringsubstr(constints,constintlen);}字符串物理实现存储结构：顺序存储结构（顺序字符串）

链式存储结构（链式字符串）字符串运算：模式匹配字符串顺序存储方式 字符串的顺序存储结构，具体又可分为静态和动态两种情况。其共同特点为：使用空间： 一块连续的存储空间关系表示： 物理相邻表示逻辑相邻元素访问： 通过下标（相对地址）读写字符串顺序存储方式 字符串（线性表）的顺序存储方式最少需要表示两方面的信息：记录分配给串的连续空间首地址＋长度连续空间的当前使用情况当前表长字符串顺序存储方式对于当前使用情况有两种表示方式：加一个特殊的末尾标记，如：’\0’记录串长度用S[0]作为记录串长的存储单元 缺点：串的最大长度不能超过256另辟一个整型存储单元存储串的长度字符串顺序存储方式对于分配给串的连续空间有两种实现方式固定长度连续空间——静态顺序存储 空间长度在定义是确定，使用期间空间大小不变；可变长度连续空间——动态顺序存储 空间长度在定义是确定，使用期间空间可以根据需要扩充。字符串顺序存储方式字符串的静态顺序存储两种实现方式：利用数组和整型常量利用指针和动态内存分配字符串顺序存储方式串的静态顺序存储——利用数组constintMsize=100;template<classT>classS1_arrString{ T s[Msize]; //以‘/0’为串结束符 //int curlen;public:

…}字符串顺序存储方式串的静态顺序存储——利用数组（例）c/c++语言标准字符串是采用的静态顺序存储方案的典型代表。其特点是 直接采用字符数组存储字符串，chars[M]; 串长最大不能超过M-1，以‘/0’作为串结束标记标准库<string.h>(C)/<cstring.h>(C++)提供了处理串的函数.1.串长 intstrlen(char*s);2.串复制 char*strcpy(char*s1,char*s2);3．串拼接 char*strcat(char*s1,char*s2);4．串比较 intstrcmp(char*s1,char*s2);5．输入和输出函数6．定位函数

char*strchr(char*s,charc);7．右定位函数char*strrchr(char*s,charc);//标准串运算实现——串比较intstrcmp(constchar*s1,constchars2){inti=0;while(s2[i]!=‘\0’||s1[i]!=‘\0’){if(s1[i]>s2[i])return1;else if(s1[i]<s2[i])return-1;i++;}if(s1[i]==‘\0’&&s2[i]!=‘\0’)return-1;else if(s1[i]!=‘\0’&&s2[i]==‘\0’)return1; else retrun0;}字符串顺序存储方式串的静态顺序存储——利用指针template<classT>classS2_arrString{ T *s; //以‘/0’为串结束符int msize; //int curlen;public:

…}字符串顺序存储方式串的静态顺序存储——评价适合访问/查找串中单个字符或连续的一组字符子串；进行插入和删除（增减字符）操作效率差，需要移动插入或删除点后面的所有字符；由于存储串的数组是静态定长的，可能在操作中出现溢出。字符串顺序存储方式字符串的动态顺序存储——利用指针template<classT>classarrString{ T *str; //以‘/0’为串结束符int size;public: …}字符串顺序存储方式疑问：它和利用指针实现的静态顺序存储有什么区别？数据成员上没有区别，函数成员有区别静态方式在操作中串空间不足时，直接溢出结束；动态方式在串空间不足时会，给串空间进行动态扩充，当扩充失败才溢出结束。s1str:size:5……Hello\0012345s1str:size:10……Hello\0012345Helloworld\001234567891011字符串顺序存储方式字符串顺序存储方式串的动态顺序存储（例）c++语言除了标准字符串之外，还提供了String类，是采用的动态顺序存储方案。根据需要申请空间；以‘/0’作为串结束标记；下面给出String类的定义和部分函数的实现//动态顺序存储类定义template<classcharT>classString{private: charT* str;int size;public://创建新字符串String(char*s=‘’); //以标准字符串s拷贝为初值String(Strings); //以标准字符串s拷贝为初值//销毁本串，从计算机存储空间删去本串~String();//赋值操作=String&operator=(char*s); //标准串s拷贝到本串String&operator=(String&s); //串s复制到本串//拼接函数＋Stringoperator＋(char*s); //本串拼接标准串s

Stringoperator＋(String&s); //本串拼接串s

//友函数作为拼接函数+其返回值是一个实例串//等于标准串str拼接串sfriendStringoperator+(char*s1,String&s);//‘关系’函数，用于比较相等、大、小，例如intoperator<(char*s); //本串小于标准串s返回非0intoperator<(String&s); //本串小于串s返回非0

friendintoperator<(char*s1,String&s);//友元函数

//‘输入输出’函数>>和<<以及读子串等，例如友函数friendistream&operator>>(isteream&istr,String&s);friendostream&operator<<(osteream&istr,String&s);//‘子串函数’：插入子串、寻找子串、//提取子串、删除子串等，例如StringSubstr(intindex，intcount);//‘串与字符’函数：按字符定位等，例如//在本串中寻找字符c,从下标start开始找,//寻找到c后,返回字符c在本串的下标位置intFind(charc,intstart);//其他函数：求串长、判空串、清为空串、intstrlen(); //返回本串的当前串长intIsEmpty(); //判本串为空串?voidclear(); //清本串为空串};//动态顺序存储类定义template<classcharT>classString{private: charT* str;int size;public://创建新字符串String(char*s=‘’); //以标准字符串s拷贝为初值String(Strings); //以标准字符串s拷贝为初值//销毁本串，从计算机存储空间删去本串~String();//赋值操作=String&operator=(char*s); //标准串s拷贝到本串String&operator=(String&s); //串s复制到本串//拼接函数＋Stringoperator＋(char*s); //本串拼接标准串s

Stringoperator＋(String&s); //本串拼接串s

//友函数作为拼接函数+其返回值是一个实例串//等于标准串str拼接串sfriendStringoperator+(char*s1,String&s);//‘关系’函数，用于比较相等、大、小，例如intoperator<(char*s); //本串小于标准串s返回非0intoperator<(String&s); //本串小于串s返回非0

friendintoperator<(char*s1,String&s);//友元函数

//‘输入输出’函数>>和<<以及读子串等，例如友函数friendistream&operator>>(isteream&istr,String&s);friendostream&operator<<(osteream&istr,String&s);//‘子串函数’：插入子串、寻找子串、//提取子串、删除子串等，例如StringSubstr(intindex，intcount);//‘串与字符’函数：按字符定位等，例如//在本串中寻找字符c,从下标start开始找,//寻找到c后,返回字符c在本串的下标位置intFind(charc,intstart);//其他函数：求串长、判空串、清为空串、intstrlen(); //返回本串的当前串长intIsEmpty(); //判本串为空串?voidclear(); //清本串为空串};//动态顺序存储类定义template<classcharT>classString{private: charT* str;int size;public://创建新字符串String(char*s=‘’); //以标准字符串s拷贝为初值String(Strings); //以标准字符串s拷贝为初值//销毁本串，从计算机存储空间删去本串~String();//赋值操作=String&operator=(char*s); //标准串s拷贝到本串String&operator=(String&s); //串s复制到本串//拼接函数＋Stringoperator＋(char*s); //本串拼接标准串s

Stringoperator＋(String&s); //本串拼接串s

//友函数作为拼接函数+其返回值是一个实例串//等于标准串str拼接串sfriendStringoperator+(char*s1,String&s);//‘关系’函数，用于比较相等、大、小，例如intoperator<(char*s); //本串小于标准串s返回非0intoperator<(String&s); //本串小于串s返回非0

friendintoperator<(char*s1,String&s);//友元函数

//‘输入输出’函数>>和<<以及读子串等，例如友函数friendistream&operator>>(isteream&istr,String&s);friendostream&operator<<(osteream&istr,String&s);//‘子串函数’：插入子串、寻找子串、//提取子串、删除子串等，例如StringSubstr(intindex，intcount);//‘串与字符’函数：按字符定位等，例如//在本串中寻找字符c,从下标start开始找,//寻找到c后,返回字符c在本串的下标位置intFind(charc,intstart);//其他函数：求串长、判空串、清为空串、intstrlen(); //返回本串的当前串长intIsEmpty(); //判本串为空串?voidclear(); //清本串为空串};//构造实现template<classcharT>String::String(char*s=‘’){ size=strlen(s);str=newchar[size+1];assert(str!=‘\0’);strcpy(str,s);}作用相当于：

if(str!=‘\0’)

return;字符串顺序存储方式取子串函数实现pos+len-1

curLen-1pos+len-1

curLen//取子串函数实现template<classcharT>StringString::Substr(intpos,intn){inti;intleft=size–pos;Stringtmp;char*p,*q;if(pos>=size) returnNULL;if(n>=left) n=left;delete[]tmp.str;tmp.str=newchar[n+1];assert(tmp.str!=NULL);p=tmp.str;q=&str[pos];for(i=0;i<n;i++)*p++=*q++;*p=‘\0’;tmp.size=n;returntmp;}//取子串函数实现template<classcharT>StringString::Substr(intpos,intn){inti;intleft=size–pos;Stringtmp;char*p,*q;if(pos>=size) returnNULL;if(n>=left) n=left;delete[]tmp.str;tmp.str=newchar[n+1];assert(tmp.str!=NULL);p=tmp.str;q=&str[pos];for(i=0;i<n;i++)*p++=*q++;*p=‘\0’;tmp.size=n;returntmp;}字符串顺序存储方式作业实现string类的其它成员函数注意：其数据成员str的空间使用问题字符串链式存储方式 链串是变长非顺序存储结构。单链表、双向链表、循环链表和静态链表等线性表实现结构都可以用于实现链式串，一般使用的是带头结点的单链表。使用空间： 连续/非连续的存储空间关系表示： 指针/下标（静态链表）元素访问： 通过指针/下标读写字符串链式存储方式用单链表方式来存储串值，串的这种链式存储结构简称为链串。其结点结构为：一个链串由头指针唯一确定。classnode{ char data; node *next;};字符串链式存储方式链串评价优点 解决了顺序串上的插入和删除操作不方便，需要移动大量的字符的问题；缺点 存储空间利用率太低。字符串链式存储方式改进链串为提高存储密度，可使每个结点存放多个字符通常将结点数据域存放的字符个数定义为结点的大小；显然，当结点大小大于1时，串的长度不一定正好是结点的整数倍，因此要用特殊字符(‘\0’)来填充最后一个结点，以表示串的终结。字符串链式存储方式改进链串——实现对于结点大小不为1的链串，其类型定为义只需对上述的结点类型做简单的修改即可。constintnodesize=80;classnode{ chardata[nodesize]; node*next;};字符串链式存储方式改进链串——评价优点是提高空间利用率；问题是单个结点所包含的字符个数的确定设置过大有可能变为顺序存储，小了空间利用率提高不明显。设置的一般规律是当串长较大时结点可适当设大一些，反之设小一些。字符串存储方式总结:当字符串临时存储时，使用顺序存储当字符串长期存储时（文件），使用链式存储（链结点为物理块）。字符串的模式匹配子串定位运算（主串中找子串位置）又称为模式匹配(PatternMatching)或串匹配(StringMatching)在串匹配中，一般将主串称为目标串，子串称之为模式串。字符串的模式匹配此运算的应用——非常广泛典型的例子有文本编辑和DNA分析。例如，在文本编辑程序中，我们经常要查找某一特定单词在文本中出现的位置。显然，解此问题的有效算法能极大地提高文本编辑程序的响应性能。字符串的模式匹配模式匹配分类精确匹配（exactmatching）近似匹配（approximatematching）字符串的模式匹配模式匹配分类——精确匹配定义 如果在目标T中至少一处存在模式P，则称匹配成功，否则即使目标与模式只有一个字符不同也不能成为匹配成功，即匹配失败。字符串的模式匹配模式匹配分类——精确匹配模式串可以是多种形式：单选（不带有通配符），如：set;多选（带有通配符），如：s?t;复杂的模式可以采用正则表达式。本节的模式不涉及通配符和正则表达式字符串的模式匹配模式匹配分类——近似匹配如果模式P与目标T（或其子串）存在某种程度的相似，则认为匹配成功。常用的衡量字符串相似度的方法是根据一个串转换成另一个串所需的的基本操作的数目来确定的。基本操作由字符串的插入、删除和替换来组成本节的模式不涉及近似匹配字符串的模式匹配模式匹配(patternmatching)已知：一个目标对象T（字符串）一个模板（pattern）P（字符串）任务：求出T中第一个与P全同匹配的子串（简称为“配串”），返回其首字符位置字符串的模式匹配 T t0t1…titi+1ti+2…ti+m-2ti+m-1…tn-1 ‖‖‖‖‖ P

p0p1p2…pm-2pm-1为使模式P与目标T匹配，必须满足：p0p1p2…pm-1=titi+1ti+2…ti+m-1字符串的模式匹配字符串的模式匹配算法主要有两种：朴素模式匹配算法KMP模式匹配算法朴素模式匹配朴素的模式匹配算法的基本思想穷举即：将目标串中所有与模式串等长的子串都比较一遍。T=P=ababababababbabababbabababbabababbabababbabababbabababbabababbXXXXXX√//朴素模式匹配#include<String.h>#include<assert.h>intNaiveStrMatching(constString&T,constString&P){inti=0;intj=0;intpLen=P.length();inttLen=T.length();if(tLen<pLen)return(-1);while(i<pLen&&j<tLen){if(T[j]==P[i]) i++,j++;else{ j=j–i+1;i=0;}}if(i>=pLen)return(j–pLen+1);elsereturn(-1);}//朴素模式匹配#include<String.h>#include<assert.h>intNaiveStrMatching(constString&T,constString&P){inti=0;intj=0;intpLen=P.length();inttLen=T.length();if(tLen<pLen)return(-1);while(i<pLen&&j<tLen){if(T[j]==P[i]) i++,j++;else{ j=j–i+1;i=0;}}if(i>=pLen)return(j–pLen+1);elsereturn(-1);}朴素模式匹配朴素模式匹配最佳示例比较|P|次，时间代价O(|P|)01234567890123456789aaaaaaaaaaaaaaaaaaabaaaaa评价不同情况下朴素模式匹配算法的比较次数不同即时间代价不同。朴素模式匹配朴素模式匹配失败最佳示例比较(|T|-|P|+1)次，时间代价O(|T|-|P|+1)01234567890123456789aaaaaaaaaaaaaaaaaaabhhhhbhhhhbhhhhb……hhhhb评价朴素模式匹配朴素模式匹配最差佳示例比较|P|(|T|-|P|+1)次，时间代价O(|T||P|)01234567890123456789aaaaaaaaaaaaaaaaaaabaaaabaaaabaaaab……aaaab评价朴素模式匹配评价最坏情况下的时间复杂度为O(|T||P|)。这种最坏的情况很少出现在文本中，经常出现在DNA信息或图像信息中。能否改进？朴素模式匹配改进理论上的推导利用目标和模式串中字符的分布概率可以估算出平均比较次数为：2(|T|-|P|+1)<2|T|利用马尔可夫链（MarkovChain）的有关理论，可以估算出更好的平均比较次数为(|A||P|+1-|A|)/(|A|-1)其中，|A|是字符串中允许使用的字符个数012345678901234567Tabacaabaccabacabaa1abacab2abacab3abacab4abacab5abacab6abacab7abacab8abacab9abacab10abacab11abacab0123456789Tabacaabacc1abacab2abacab3abacab4abacab5abacab朴素模式匹配改进信息在朴素模式匹配的比较过程中有一部分字符之间的比较可以转换成模式串自身字符和自身字符的比较。而模式串自身字符之间的比较可以通过事先处理模式串，从而事先确知它们的比较结果，从而减少匹配时的比较次数。朴素模式匹配改进什么时候可以利用模式串自身和自身字符关系来减少比较的次数？我们来考虑一般情况下的情况，假设：目标串T和模式串P从Tj-i出开始匹配到Tj处发生失配。朴素模式匹配改进 T T0T1…Tj-i-1Tj-iTj-i+1…Tj-2Tj-1Tj…Tn-1

‖‖‖‖ P P0P1…Pi-2Pi-1Pi

则有：Tj-iTj-i+1…Tj-1=P0P1…Pi-1(1)朴素模式匹配改进如果P0P1…Pi-2=P1P2…Pi-1(2)

则立刻可以断定P0P1…Pi-2

=Tj-i+1Tj-i+2…Tj-1

此时直接比较Pi-1和Tj即可。（相当于将模式串右移一位继续比较）朴素模式匹配改进…Tj-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1…Pi-2Pi-1Pi…P0…Pi-1Pi-2Pi-1Pi…====X朴素模式匹配改进

如果(2)不成立，即P0P1…Pi-2

P1P2…Pi-1

则继续考虑P0P1…Pi-3

=P2P3…Pi-1 (3)

若成立直接比较Pi-2和Tj即可。（相当于将模式串右移两位继续比较）朴素模式匹配改进…Tj-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1P2…Pi-3Pi-2Pi-1Pi…P0P1P2…Pi-3Pi-2Pi-1Pi…=====X朴素模式匹配改进

如果(3)不成立，即P0P1…Pi-3

P2P3…Pi-1

则继续考虑

P0P1…Pi-4

=P3P4…Pi-1 (3)

以此类推朴素模式匹配改进直到对于某一个“k”值，使得P0P1…Pi-k-1=PkPk+1…Pi-1成立，此时将模式串右移k位继续比较Pi-k和Tj即可。朴素模式匹配改进…Tj-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1…Pi-k-1Pi-k…PkPk+1…Pi-1Pi…P0P1…Pi-k-1Pi-k…PkPk+1…Pi-1Pi…====X朴素模式匹配改进特别的： k最大可以等于i，这是意味着不存在这样相等的子串，直接移动i位继续比较P0和Tj即可。…Tj-iTj-i+1…Tj-2Tj-1TjTj+1…P0P1P2…Pi-3Pi-2Pi-1Pi…X朴素模式匹配改进结论由此可见，根据模式串本身的特征，就可以确定在某趟发生发生失配时模式串应该右移的位数，在失配处开始下趟匹配。这样既保证不丢失匹配串，又不需要在目标串回溯，从而消除冗余比较。朴素模式匹配改进当模式串在某字符处失配时，如何确定模式串右移的位数（或移至哪一位）？由于模式串的每一个字符都有可能在匹配过程中失配，所以使用字符串的特征向量 来表示。字符串的特征向量预备定义把P的前k个字符组成的子串P(0...k-1)称为P的前缀子串（也称“串首”）；把P在i之前的k个字符组成的子串P(i-k...i-1)称为i位置的后缀子串（也称“尾串‘）。字符串的特征向量定义设：模式串中P(0...i-1)存在最长为k的前缀子串和后缀子串相等；当i位置的字符Pi与主串中字符Tj失配时，则模式串的下标从位置i移动到位置k（向右移动了i-k位），让Pk与Tj继续比较；我们将k称为字符Pi的特征数，记为ni；字符串的特征向量特征向量整个模式串所有字符的特征数合称为模式串的特征向量，记为next。计算公式字符串的特征向量特征向量问题：该公式的计算效率比较低？因为为了找到k值，需要不断的判断P(0‥k-1)和P(i-k‥i-1)是否相等，这个判断过程相当于进行朴素模式匹配。字符串的特征向量改进的特征向量计算我们注意到当计算next[i]时，next[0‥i-1]都已计算完成，而为了计算next[i]而进行的P(0‥k-1)和P(i-k‥i-1)的比较，完全可以利用next[0‥i-1]来计算。即：利用next[0‥i-1]计算next[i]

。改进的特征向量计算——next[i]的递归定义如果i=0，则next[i]=-1；令k=next[i-1]

，如果i>01、如果Pi-1=Pk，则next[i]=k+1；2、如果Pi-1

≠Pk&&

k≠0，令k=next[k]如果Pi-1=Pk

，则转1处理；如果k=0，则转3处理；否则，转2处理；3、如果Pi-1

≠Pk&&k=0，则next[i]=0。例：计算模式串”abcdaabcab”的next数组字符串的特征向量0123456789Pabcdaabcabnext-1000011231字符串的特征向量再改进next在利用next进行模式匹配时，当有Pi

≠Tj，则应转向Pnext[i]

与Tj继续比较；如果有Pi=Pnext[i]，则Pnext[i]

≠Tj必然成立，则可将next[i]

修改为next[next[i]]。如果还相等则继续利用next向前推，直至-1为止字符串的特征向量0123456789Pabcdaabcabnext-10000112310123456789Pabcdaabcabnext-1000-110030//特征向量计算#include<String.h>#include<assert.h>int*findNext(StringP){inti=0;intk=-1;intm=P.length();assert(m=0);int*next=nextint[m];assert(next!=0);next[0]=-1;while(i<m){ while(k>=0&&P[i]!=P[k]) k=next[k]; i++; k++; if(i==m) break; if(P[i]==P[k]) next[i]=next[k]; else next[i]=k;}returnnext;}//特征向量计算#include<String.h>#include<assert.h>int*findNext(StringP){inti=0;intk=-1;intm=P.length();assert(m=0);int*next=nextint[m];assert(next!=0);next[0]=-1;while(i<m){ while(