北京化工大学数据结构2022/10/13作业 题解

目录

问题 A: 字符串变换

问题 B: 字符串求反

问题 C: 字符串转化为整数（附加代码模式）

问题 D: 字符串匹配（朴素算法）-附加代码模式

问题 E: 求解最长首尾公共子串-附加代码模式

问题 F: 算法4-7：KMP算法中的模式串移动数组-附加代码模式

问题 G: 数据结构作业03 -- 改进的nextVal向量

问题 H: 算法4-6：字符串匹配算法执行次数比较（朴素、KMP、改进的KMP）-附加代码模式

问题 A: 字符串变换

依据题意，只可以在末尾增加或删除

所以如果ab串长度不相等，要先用|m-n|步将两字符串补齐

当然，补的那部分天然相等

所以在改这步中，我们只需要比较m，n短的那个，每个不同加一步即可

signed main(){int m,n;cin>>m>>n;string a,b;cin>>a>>b;int t=0;t+=fabs(m-n);for(int i=0;i<min(m,n);i++)if(a[i]!=b[i])t++;cout<<t;return 0;
}

问题 B: 字符串求反

这。。。。应该没啥好说的

signed main(){string a;cin>>a;reverse(a.begin(),a.end());cout<<a.size()<<'\n'<<a;
}

问题 C: 字符串转化为整数（附加代码模式）

从后往前遍历即可

k代表当前这个数后面有几个0

int str2int(const char a[],int &data){int m=strlen(a);data=0; int k=1;for(int i=m-1;i>=0;i--){if(a[i]>='0'&& a[i]<='9'){int now=(a[i]-'0')*k;data+=now;k=k*10;}else{return 1;}}return 0;   
}

问题 D: 字符串匹配（朴素算法）-附加代码模式

朴素算法，每一位匹配一遍即可，匹配成功就返回当前位置

代码如下

#define max 1000000
int findPos(char s[], char t[]){int m=strlen(s);int n=strlen(t);if(m<n){return -1;}for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(s[i+j]!=t[j]){break;}if(j==n-1){return i;}}}return -1;
}

问题 E: 求解最长首尾公共子串-附加代码模式

最长首位公共子串是什么？

首先前缀子串和后缀子串大家应该都不陌生

比如abacab这个串

a，ab，aba，abac，abaca这叫前缀

b，ab，cab，acab，bacab这叫后缀

最长首位公共子串就是在等于前缀的后缀中最长的那个

很显然是ab

 那么如何求这个最长首尾公共子串呢

我们只需要两个指针，j去找匹配的后缀

k与j比对找与之匹配的前缀

如果相等，那么都往后走一步

如果j走到了末尾，那么很显然此时k就是答案

如果还没走到末尾就断了，那么k就要退回到ne[k]

代码如下

int ne[100000];
#define max 1000000
int calcLCT(char t[]){int n=strlen(t);if(n==1){return -1;}ne[0]=-1;int k=ne[0];int j=0;while(j<n){if(k==-1||t[j]==t[k]){j++;k++;ne[j]=k;}else{k=ne[k];}}return ne[n];
}

问题 F: 算法4-7：KMP算法中的模式串移动数组-附加代码模式

算法同上

毕竟next数组的本质就是当前匹配到的最长前后公共子串

#define max 1000000
void getNext(char t[], int ne[]){int k=-1;ne[0]=-1;int len=strlen(t);int j=0;while (j<len-1){if (k==-1||t[k]==t[j]){k++;j++;ne[j]=k;}else{k = ne[k];}}
}

问题 G: 数据结构作业03 -- 改进的nextVal向量

原next数组的问题：

 也就是说，如果按原next回溯，回溯到的值与目前的值一样，那不白回溯了吗

原来就是因为C和B不相等才回溯的，你回溯完之后还是B，那不照样不相等吗

所以我们就要预处理一下nextval，如果回溯的值相等，那我们就要再往深层回溯

直至回溯之后与当前不相等

nextval与原next的关系：

如果位置k的元素与next[k]元素相同时，nextval[k]=nextval[next[k]]

如果位置k的元素与next[k]元素不同时，nextval[k]= next[k]

代码如下： 

using namespace std;
void CalcNextVal(char p[],int ne[])
{int i=0;int j=-1;ne[i]=j;int len=strlen(p);while(i<len){if(j==-1||p[i]==p[j]){i++;j++;if(p[i]==p[j]){ne[i]=ne[j];}else{ne[i]=j;}}else{j=ne[j];}}
}
char s[1000000];
int ne[1000000];
signed main()
{while(cin>>s){CalcNextVal(s,ne);int len2=strlen(s);fer(i,0,len2-1){cout<<ne[i]<<" ";}cout<<'\n';}
}

问题 H: 算法4-6：字符串匹配算法执行次数比较（朴素、KMP、改进的KMP）-附加代码模式

这题基本是以上代码的结合体

又是一道码农题

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define max 1000000
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
int findPos(char S[], char T[]){int res=0;int lens=strlen(S);int lent=strlen(T);int i=0,j=0;while(i<lens&&j<lent){res++;if(S[i]==T[j]){i++;j++;}else{i-=j-1;j=0;}}cout<<"count in findPos is:"<<res<<endl;if(j>=lent){return i-j;}else{return -1;}
}
void CalcNext(char T[],int ne[]){int i=0,k=-1;ne[0]=-1;while(i<strlen(T)) {if (k==-1||T[i]==T[k]) {i++;k++;ne[i]=k;}else{k=ne[k];}}
}
void CalcNextVal(char T[],int ne[],int neVal[]){int l=strlen(T);fer(i,0,l-1){neVal[i]=ne[i];}fer(i,0,l-1){int k=ne[i];if(T[i]==T[k]){neVal[i]=neVal[k];}}
}
int findPos_kmp(char S[], char T[], int ne[]){int res=0;int lens=strlen(S);int lent=strlen(T);int i=0,j=0;while(i<lens&&j<lent){res++;if(S[i]==T[j]||j==-1){i++;j++;}else{j=ne[j];}}cout<<"count in findPos_kmp is:"<<res<<endl;if(j>=lent){return i-lent;}else{return -1;}
}