串

知识框架

** 串的基本操作 **

1. StrAssion(&T,chars) ; 赋值操作,将串 T 赋值为 chars 。
2. StrCompare(S,T) ;比较操作。
3. Strlength(S) ; 求串的长度。
4. Concat(&T,S1,S2) : 串连接。用T返回由S1和S2连接而成的新串。

类型声明 :

typedef struct{	char data[MaxSize];int length;			//串长
} SqString;

1 生成串

void StrAssign(SqString &s,char cstr[])	{ //字符串常量赋给串sint i;for (i=0;cstr[i]!='\0';i++)s.data[i]=cstr[i];s.length=i;
}

2 串的比较

bool StrCompare(SqString s,SqString t)	//判串相等
{bool same = true;int i;if (s.length!=t.length)				//长度不相等时返回0same=false;else for (i=0;i<s.length;i++)if (s.data[i]!=t.data[i])	//有一个对应字符不相同时返回0{	same=false;break;}return same;
}

3 求串长

int StrLength(SqString s){return s.length ; 
}

4 串的连接

SqString Concat(SqString s , SqString t ){// 串连接SqString str ; str.length = s.length + t.length ; for(int i = 0 ; i<s.length ;i++){str.data[i] = s.data[i] ; }for(int i = 0 ; i<t.length ;i++){str.data[s.length+i] = t.data[i] ; }return str ; 
}

5 求子串

SqString SubStr(SqString s ,int i , int j ){// 求子串 从i开始长度为jSqString str; str.length = 0 ; if(i <=0 || i>s.length || j <0 || i+j-1>s.length) {return str ; }for(int k = i- ; k<i+j-1 ; k++ ) {str.data[k-i+1] = s.data[k] ; }str.length = j ; return str ; 
}

6 插入操作

SqString InsertStr(SqString s1 , int i , SqString s2 ) {// 返回SqString str ; str.length = 0 ; if (i<=0 || i>s1.length+1)  //参数不正确时返回空串return str;for(int j = 0 ; j<i-1 ; j++ ) {str.data[j] = s1.data[j] ; }for(int j = 0 ; j<s2.length ; j++) {str.data[i+j-1] = s2.data[j] ; }for(int j = i - 1 ; j<s1.length ; j++) {str.data[s2.length +j] = s1.data[j] ; }str.length = s1.length + s2.length ; return str ; 
}

测试代码 :

#include <iostream>
#include <cstring>
#include <cstdlib>
#define MaxSize 1005
using namespace std ;
// 顺序串
typedef struct {char data[MaxSize] ;int length ;  
}SqString ; 
void StrAssign(SqString &s , char chars[]) {int i = 0 ; while(chars[i]!='\0'){s.data[i] = chars[i] ;s.length++ ;  i++ ; }
}
void StrCopy(SqString &s , SqString t) {for(int i = 0 ; i<t.length ; i++ ) {s.data[i] = t.data[i] ; }s.length = t.length ; 
}
bool StrCompare(SqString s , SqString t) {bool ans = true ; if(s.length != t.length) return false  ;else{for(int i = 0 ; i<s.length ;i++) {if(s.data[i]!=t.data[i]){ans = false ; break ; }}}return ans ; 
}
int StrLength(SqString s ){return s.length ; 
}
SqString Concat(SqString s , SqString t ){// 串连接SqString str ; str.length = s.length + t.length ; for(int i = 0 ; i<s.length ;i++){str.data[i] = s.data[i] ; }for(int i = 0 ; i<t.length ;i++){str.data[s.length+i] = t.data[i] ; }return str ; 
}
SqString SubStr(SqString s ,int i , int j ){// 求子串 从i开始长度为jSqString str; str.length = 0 ; if(i <=0 || i>s.length || j <0 || i+j-1>s.length) {return str ; }for(int k = i- 1; k<i+j-1 ; k++ ) {str.data[k-i+1] = s.data[k] ; }str.length = j ; return str ; 
}
SqString InsertStr(SqString s1 , int i , SqString s2 ) {// 返回SqString str ; str.length = 0 ; if (i<=0 || i>s1.length+1)  //参数不正确时返回空串return str;for(int j = 0 ; j<i-1 ; j++ ) {str.data[j] = s1.data[j] ; }for(int j = 0 ; j<s2.length ; j++) {str.data[i+j-1] = s2.data[j] ; }for(int j = i - 1 ; j<s1.length ; j++) {str.data[s2.length +j] = s1.data[j] ; }str.length = s1.length + s2.length ; return str ; 
}
void DispStr(SqString s)	//输出串s
{int i;if (s.length>0){	for (i=0;i<s.length;i++)printf("%c",s.data[i]);printf("\n");}
}
SqString DelStr(SqString s,int i,int j)		//串删去
{int k;SqString str;str.length=0;if (i<=0 || i>s.length || i+j>s.length+1) //参数不正确时返回空串return str;for (k=0;k<i-1;k++)       		//将s.data[0..i-2]复制到strstr.data[k]=s.data[k];for (k=i+j-1;k<s.length;k++)	//将s.data[i+j-1..s.length-1]复制到strstr.data[k-j]=s.data[k];str.length=s.length-j;return str;
}
SqString RepStr(SqString s,int i,int j,SqString t)	//子串替换
{int k;SqString str;str.length=0;if (i<=0 || i>s.length || i+j-1>s.length) //参数不正确时返回空串return str;for (k=0;k<i-1;k++)				//将s.data[0..i-2]复制到strstr.data[k]=s.data[k];for (k=0;k<t.length;k++)   		//将t.data[0..t.length-1]复制到strstr.data[i+k-1]=t.data[k];for (k=i+j-1;k<s.length;k++)	//将s.data[i+j-1..s.length-1]复制到strstr.data[t.length+k-j]=s.data[k];str.length=s.length-j+t.length;return str;
}
int main() {SqString s ;char t[100] = "helloworld" ; StrAssign(s,t);DispStr(s);DispStr(SubStr(s,2,4) );return 0 ; 
}

串的模式匹配

简单的模式匹配

算法 : 分别用计数指针 i 和 j 分别指示主串 S 和模式串 T中当前正待比较的字符位置。

从主串S的第一个字符开始,与模式串T的第一个字符比较,若相等,则继续逐个比较后续字符;否则从主串的下一个字符起,重新和匹配的字符比较;以此类推,直至模式T中的每一个字符和主串的每个连续字符序列相等,则匹配成功。

否则匹配失败。

模式T = 'abcac’ 和主串 S 的匹配过程如上,每次匹配失败,都把模式T后移一位。

// 暴力破解
int index(char *s ,char *t)
{// s是主串 , t 是匹配串int lens = strlen(s) ;int lent = strlen(t) ;int  i = 0 , j = 0 ;while(i<lens && j<lent){if(s[i]==t[j]){i++;j++;}else{i = i -j + 1 ;j=0 ;}}if(j== lent){return i-j ;}else{return -1 ;}}

KMP算法

我们发现,在第三趟匹配中, i = 7 , j = 5 的字符比较不等,于是又从 i = 4 , j = 1 重新开始比较。然而仔细观察发现,第4趟和第5趟,以及 i = 6 ,j = 1 是没必要比较的。在第三趟比较的时候, 主串的‘a’ ,’b’ ,’c’ ,’a’ 和 匹配串中的‘a’ ,’b’ ,’c’ ,’a’ ’已经匹配成功了。

字符的前缀、后缀、和部分匹配值

前缀 : 除最后一个字符以外,字符串的所有头部子串;

后缀 : 除了第一个字符以外,字符串的所有尾部子串;

部分匹配值 : 字符串的前缀和后缀的最长相等前缀后缀长度 ;

以 'ababa’为例 :

• 'a’ 的前缀和后缀都是空集,最长相等前后缀长度为0 ;
• ‘ab’ 的前缀为 {a} , 后缀为 {b} , {a} $\bigcap $ {b} =$\varnothing $,最长相等前后缀长度为0 ;
• ‘aba’ 的前缀为 { a ,ab } , 后缀为 {a,ba} , {a,ab} $\bigcap $ {a , ba} = {a} , 最长相等前后缀长度为 1 ;
• 'abab’ 的前缀为 { a, ab , aba } , 后缀为 {b , ab , bab} , 交集为 {ab} , 最长相等前后缀为 2 ;
• ‘ababa’ 的前缀为{a , ab , aba , abab } , 后缀为 { a, ba , aba , baba } 交集为 {a,aba} ,长度为 3 ;

得到部分匹配表 :

编号	1	2	3	4	5
S	a	b	a	b	a
PM	0	0	1	2	3

---

‘abcac’的部分匹配值

编号	1	2	3	4	5
S	a	b	c	a	c
PM	0	0	0	1	0

下面使用得到的 next 数组进行字符串匹配 :

主串 : a b a b c a b c a c b a b

子串 : a b c a c

第一趟匹配 :

发现 a 和 c 匹配失败 ,前面的2个字符 ‘ab’ 是匹配的,最后一个匹配字符 b 对应的部分匹配值为 0 ,子串需要移动的位数 :
$移动位数 = 已经匹配的字符数 - 对应的部分匹配值(next)$
所以移动 2 - 0 = 2 ,

主串 : a b a b c a b c a c b a b

子串 : a b c a c

继续第二趟匹配:

发现 b 和 c 匹配失败 , 子串移动 4 - 1 = 3 步。

主串 : a b a b c a b c a c b a b

子串 : a b c a c

匹配成功!!!