串
例1-1
设计顺序串上实现串比较运算 strcmp(s,t)的算法。 ab<abcd，abcd<abd
解：算法思路如下：
(1)比较s和t两个串共同长度范围内的对应字符：
①若s的字符>t的字符，返回1；
②若s的字符<t的字符，返回-1；
③若s的字符=t的字符，按上述规则继续比较。
(2)当(1)中对应字符均相同时，比较s和t的长度：
①两者相等时，返回0；
②s的长度>t的长度，返回1；
③s的长度<t的长度，返回-1。
int Strcmp(SqString s,SqString t){
int i,comlen;
if(s.length<t.length) comlen=s.length; //求s和t的共同长度
else comlen=t.length;
for(i=0;i<comlen;i++)
if(s.data[i]>t.data[i])
return 1;
else if(s.data[i]<t.data[i])
return -1;
if(s.length=t.length)
return 0; //s==t
else if(s.length<t.length)
return 1; //s>t
else return -1; //s<t
}
例1-2
在链串中，设计一个算法把最先出现的子串”ab”改为”xyz”。
解：
①查找：p->data=’a’ && p->next->data=’b’
②替换：
void Repl(LiString *&s){
LiString *p = s->next,*q;
int find = 0;
while(p->next!=NULL && find==0){ //查找ab子串
if(p->data=='a'&&p->next->data=='b'){
p->data='x';p->next->data='z';
q=(LiString *)malloc(sizeof(LiString));
q->data='y';q->next=p>next;p->next=q;
find=1;
}
else p=p->next;
}
}
模式匹配
Brute-Force——BF算法，简单匹配算法。时间复杂度 O(n*m)
int index(SqString s,SqString t){
int i=0,j=0; //i指向s，j指向t
while(i<s.length && j<t.length){
if(s.data[i] == t.data[j]){ //继续匹配下一个字符
i++; //主串和子串依次匹配下一个字符
j++;
}else{ //主串、子串指针回溯重新开始下一次匹配
i=i-j+1; //主串从下一个位置开始匹配
j=0; //子串从头开始匹配
}
}
if(j>=t.length)
return (i-t.length); //返回匹配的第一个字符的下标
else
return -1; //模式匹配不成功
}
KMP算法：消除了主串指针的回溯。平均时间复杂度为O(n+m)，最坏时间复杂度为O(n*m)
//由模式串t求next值的算法
void GetNext(SqString t,int next[]){
int j,k;
j=0;k=-1;next[0]=-1;
while(j<t.length-1){
if(k==-1||t.data[j]==t.data[k]){
j++;k++;
next[j]=k;
}
else k=next[k];
}
}
//KMP算法
int KMPIndex(SqString s,SqString t){
int next[MaxxSize],i=0,j=0;
GetNext(t,next);
while(i<s.length && j<t.length){
if(j==-1||s.data[i]==.data[j]){
i++;j++; //i、j各增1
}else
j=next[j]; //i不变，j后退
}
if(j>=t.length)
return (i-t.length); //返回匹配模式串的首字符下标
else return -1; //返回不匹配标志
}
//由模式串t求next值改为求nextval,将KMP算法中的next改为nextval
void GetNextval(SqString t,int nextval[]){
int l=nextval.length,j=1;
int next[] = new int[l];
nextval[0]=-1;
GetNext(t,next);
while(j<l){
if(t[j]==t[next[j]]){
nextval[j]=nextval[next[j]];
}else
nextval[j]=next[j];
j++;
}
}
例1-3
假设串采用顺序结构存储。设计一个算法求串s中出现的第一个最长重复子串的下标和长度。
解：(i,len)记录当前重复子串，(maxi,maxlen)记录第一个最长重复子串。
void maxsubstr(SqString s,SqString &t){
int maxi=0,maxlen=0,len,i,j,k;
i=0;
while(i<s.length){ //从下标为i的字符开始
j=i+1; //从i的下一个位置开始找重复子串
while(j<s.length){
if(s.data[i])==s.data[j]){ //找一个子串，其起始下标为i,长度为len
len=1;
for(=1;s.data[i+k]==s.data[j+k];k++) //将较大长度者赋给maxi与maxlen
len++;
if(len>maxlen){
maxi=i;
maxlen=len;
}
j+=len;
}
else j++;
}
i++; //继续扫描第i字符之后的字符
}
t.length=maxlen; //将最长重复子串赋给t
for(i=0;i<maxlen;i++)
t.data[i] = s.data[maxi+i];
}