Contest2754 - 2022年计算机类数据结构作业5.20221013-1018问题 AM: 字符串变换问题 AN: 字符串求反问题 AO: 字符串转化为整数（附加代码模式）问题 AP: 字符串匹配（朴素算法）-附加代码模式问题 AQ: 求解最长首尾公共子串-附加代码模式问题 AR: 算法4-7：KMP算法中的模式串移动数组-附加代码模式问题 AS: 数据结构作业03 -- 改进的nextVal向量问题 AT: 算法4-6：字符串匹配算法执行次数比较（朴素、KMP、改进的KMP）-附加代

75 阅读 0 评论 50 点赞

我是靠谱客的博主幸福夏天，最近开发中收集的这篇文章主要介绍Contest2754 - 2022年计算机类数据结构作业5.20221013-1018问题 AM: 字符串变换问题 AN: 字符串求反问题 AO: 字符串转化为整数（附加代码模式）问题 AP: 字符串匹配（朴素算法）-附加代码模式问题 AQ: 求解最长首尾公共子串-附加代码模式问题 AR: 算法4-7：KMP算法中的模式串移动数组-附加代码模式问题 AS: 数据结构作业03 -- 改进的nextVal向量问题 AT: 算法4-6：字符串匹配算法执行次数比较（朴素、KMP、改进的KMP）-附加代，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题 AM: 字符串变换

问题 AN: 字符串求反

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

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

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

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

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

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

问题 AM: 字符串变换

内存限制：128 MB时间限制：1.000 S

评测方式：文本比较命题人：liuyong

提交：1649解决：1229

返回比赛提交提交记录侧边提交

题目描述

定义字符串的变换规则如下：

将其中任意一个字母替换为另一个
把最后一个字母删除
在尾部添加一个字母

给定两个字符串A和B，根据上面的规则，将A变成B，最少需要多少步操作？

输入

输入包括3行，
第一行包括两个小于1000的正整数m和n，分别表示两个字符串的长度，
接下来两行每行1个字符串，每个字符串仅由大写字母组成

输出

输出最小的操作步数

样例输入复制

4 3
WXYZ
WXY

样例输出复制

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int m,n;
    cin>>m>>n;
    char a[1005],b[1005];
    for(int i=0;i<m;i++)
    cin>>a[i];
    for(int j=0;j<n;j++)
    cin>>b[j];
    int minlen=min(m,n);
    int ans=0;
    for(int i=0;i<minlen;i++)
    if(a[i]!=b[i])
    ans++;
    ans+=max(m,n)-minlen;
    cout<<ans;
}

问题 AN: 字符串求反

内存限制：128 MB时间限制：1.000 S

评测方式：文本比较命题人：liuyong

提交：4035解决：2407

返回比赛提交提交记录侧边提交

题目描述

给定一个长度不超过100的字符串，求其长度，并将其反转后输出

输入

输入包括一行长度不超过100的字符串，字符串仅由小写字母组成

输出

输出包括2行，第一行为字符串长度，第二行为字符串反转后输出结果。

样例输入复制

hello

样例输出复制

5
olleh

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin>>s;
    cout<<s.length()<<endl;
    for(int i=s.length()-1;i>=0;i--)
    cout<<s[i];
 
}

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

内存限制：128 MB时间限制：1.000 S

评测方式：文本比较命题人：liuyong

提交：869解决：630

返回比赛提交提交记录侧边提交

题目描述

输入一个字符串，将其转化为整数后输出，本题为附加代码模式，main函数代码如下，将会自动附加在提交的代码后面。

输入

字符串s，最大长度为10个字符，每个字符可能是数字或者字母；

输出

如果字符串中包含字母，则无法转化为一个数字，输出failed
如果字符串中没有包含字母，则可以转化一个整数，将其实际结果输出。
注意如果字符串是“012”，转化为整数后输出应该是12

样例输入复制

样例输出复制

提示

函数声明如下所示：

#include <iostream>

#include <cstring>

using namespace std;

// 转换成功返回0，否则返回-1

int str2int(char str[], int &data){

// write your code

}

int main()

{

char str[11];

cin>>str;

int data, result;

result = str2int(str,data);

if(result == 0){

cout << data << endl;

}else{

cout << "failed" << endl;

}

return 0;

}

#include<bits/stdc++.h>
using namespace std;
 
int str2int(char str[],int &data)
{
    int begin=0;
    for(int i=0;str[i]!='';i++)
    {
        if(str[i]!='0')
        {
            begin=i;
            break;
        }
    }
    data=0;
    for(int i=begin;str[i]!='';i++)
    {
 
        if(str[i]>='0'&&str[i]<='9')
        {
            data=data*10+int(str[i])-48;
        }
        else
        {
            return -1;
        }
    }
    return 0;
}

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

内存限制：128 MB时间限制：100.000 S

评测方式：文本比较命题人：liuyong

提交：2833解决：996

返回比赛提交提交记录侧边提交

题目描述

使用朴素的字符串匹配算法完成本题。注意本题为附加代码模式，main函数代码会自动附加在同学们提交的代码后面，请同学们提交代码的时候注释掉自己的main函数代码。
附加的main函数代码如下：
char s[max],t[max];

int main()

{

while(cin>>s>>t){

int pos = findPos(s,t);

cout << pos << endl;

}

return 0;

}

输入

输入包括多行，每行两个字符串S1 S2，用空格隔开。每个字符串长度不超过2千万

输出

对每行输入，输出S2在S1中首次匹配成功的位置，匹配不成功输出-1.

样例输入复制

111 222
001 001

样例输出复制

-1
0

提示

本题为代码填空题，主要目的是帮助同学们更好的掌握朴素的字符串匹配算法，这是进一步掌握KMP算法的基础
代码框架如下，请同学们完成代码后提交：

#include <iostream>

#include <cstring>

using namespace std;

#define max 20000000

int findPos(char s[], char t[]){

int m = strlen(s), n = strlen(t);

int i = 0, j = 0;

while(i<m && j<n){

if(s[i] == t[j]){

// write your code

}else{

// write your code

}

if(j >= n){

// write your code

}else{

// write your code

}

char s[max],t[max];

int main()

{

while(cin>>s>>t){

int pos = findPos(s,t);

cout << pos << endl;

}

return 0;

}

#include<bits/stdc++.h>
using namespace std;
#define max 20000000
 
int findPos(char s[],char t[])
{
    int m=strlen(s);
    int n=strlen(t);
    for(int i=0;i<m;i++)
    {
        int j=0;
        for(j=0;j<n;j++)
        {
            if(s[i+j]!=t[j])
            break;
        }
        if(j==n)
        {
            return i;
        }
    }
    return -1;
}
 
/*char s[max],t[max];
int main()
{
    while(cin>>s>>t)
    {
        int pos=findPos(s,t);
        cout<<pos<<endl;
    }
}*/

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

内存限制：128 MB时间限制：1.000 S

评测方式：文本比较命题人：liuyong

提交：981解决：631

返回比赛提交提交记录侧边提交

题目描述

输入一个长度不超过100的字符串，求解其最长首尾公共子串。
注意本题为附加代码模式，main函数代码会自动附加在同学们提交的代码后面，请同学们提交代码的时候注释掉自己的main函数代码。
附加的main函数代码如下：

int main()

{

char t[max];

cin >> t;

int lct = calcLCT(t);

cout << lct << endl;

return 0;

}

输入

一个长度不超过100的字符串

输出

输出其首尾最大公共子串的长度。如果该字符串只有1个字符，输出-1；否则，则可以计算其首尾最大公共子串长度并输出。

样例输入复制

aaaa

样例输出复制

提示

代码框架如下，可以拷贝后补充完整提交
#include <iostream>

#include <cstring>

using namespace std;

#define max 100

// 返回字符串t的最长首尾公共子串长度

int calcLCT(char t[]){

}

int main()

{

char t[max];

cin >> t;

int lct = calcLCT(t);

cout << lct << endl;

return 0;

}

#include<bits/stdc++.h>
using namespace std;
#define max 100
 
int calcLCT(char t[])
{
    int n=strlen(t);
    if(n==1)
    return -1;
    for(int i=1;i<n;i++)
    {
        int ans=0;
        int temp=i+1;
        int front=0;
        if(t[0]==t[i])
        {
            front++;
            while(temp<n)
            {
                if(t[temp]!=t[front])
                break;
                else
                {
                    temp++;
                    front++;
                }
            }
        }
        if(temp==n)
        {
            ans+=front;
            return ans;
        }
    }
}
 
 
/*int main()
{
    char t[max];
    cin>>t;
    int lct=calcLCT(t);
    cout<<lct<<endl;
}*/

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

内存限制：128 MB时间限制：1.000 S

评测方式：文本比较命题人：2011014323

提交：2182解决：1552

返回比赛提交提交记录侧边提交

题目描述

字符串的子串定位称为模式匹配，模式匹配可以有多种方法。简单的算法可以使用两重嵌套循环，时间复杂度为母串与子串长度的乘积。而KMP算法相对来说在时间复杂度上要好得多，为母串与子串长度的和。但其算法比较难以理解。

在KMP算法中，使用到了一个next数组。这个数组就是在比较失配时母串指针不必回溯，而子串指针移动相应位置即可。
给定一个字符串，计算next数组的递推算法如下：

next[0]=-1，从i=0开始，根据next[i]计算next[i+1]的值，具体方法为：令k=next[i],如果T[i]==T[k],则next[i+1]=k+1;如果T[i]!=T[k]，令k’=next[k],一直迭代，直到T[j]==T[k’]或者k’为-1,则next[i+1]=k’+1

本题为附加代码模式，main函数代码如下，将会自动附加在提交的代码后面。

int main()

{

// freopen("/config/workspace/answer/test.in","r",stdin);

// freopen("/config/workspace/answer/test.out","w",stdout);

char t[max];

cin >> t;

int len = strlen(t);

int next[len];

getNext(t,next);

for(int i=0;i<len;i++){

cout << next[i] << " ";

}

cout << endl;

return 0;

}

输入

一个模式串，仅由英文小写字母组成。长度不大于100。

输出

输出模式串对应的移动数组next。每个整数后跟一个空格。

样例输入复制

abaabcac

样例输出复制

-1 0 0 1 1 2 0 1

提示

代码框架如下所示,请同学们补充完整算法代码后提交：

#include <iostream>

#include <cstring>

using namespace std;

#define max 100

void getNext(char t[], int next[]){

// write your code

}

int main()

{

// freopen("/config/workspace/answer/test.in","r",stdin);

// freopen("/config/workspace/answer/test.out","w",stdout);

char t[max];

cin >> t;

int len = strlen(t);

int next[len];

getNext(t,next);

for(int i=0;i<len;i++){

cout << next[i] << " ";

}

cout << endl;

return 0;

}

#include<bits/stdc++.h>
using namespace std;
#define max 100
 
void getNext(char t[],int next[])
{
    int length=strlen(t);
    next[0]=-1;
    int i=0,j=-1;
    while(i<length)
    {
        if(j==-1||t[i]==t[j])
        next[++i]=++j;
        else
        {
            j=next[j];
        }
         
    }
}
 
/*int main()
{
    char t[max];
    cin>>t;
    int len = strlen(t);
    int next[len];
    getNext(t,next);
    for(int i=0;i<len;i++)
    cout<<next[i]<<" ";
    cout<<endl;
    return 0;
}*/

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

内存限制：128 MB时间限制：1.000 S

评测方式：文本比较命题人：外部导入

提交：3902解决：1663

返回比赛提交提交记录侧边提交

题目描述

按照改进KMP算法计算指定模式串的nextval向量。

输入

一组由字母和数字组成的模式串，每个模式串输入一行，长度不小于1，不大于200。

输出

输入每个模式串的nextval向量，每个nextval向量输出一行，各数值之间用一个空格隔开。

样例输入复制

aabb
abcabc

样例输出复制

-1 -1 1 0 
-1 0 0 -1 0 0

#include<bits/stdc++.h>
using namespace std;
#define max 300
 
void getNext(char t[],int next[])
{
    int length=strlen(t);
    next[0]=-1;
    int i=0,j=-1;
    while(i<length)
    {
        if(j==-1||t[i]==t[j])
        next[++i]=++j;
        else
        {
            j=next[j];
        }
         
    }
}
 
int main()
{
    char t[max];
    while(cin>>t)
    {
        int len = strlen(t);
        int next[max];
        getNext(t,next);
        int nextval[max];
        nextval[0]=-1;
        for(int i=1;i<len;i++)
        {
            if(t[i]==t[next[i]])
            nextval[i]=nextval[next[i]];
            else
            nextval[i]=next[i];
        }
        for(int i=0;i<len;i++)
        cout<<nextval[i]<<" ";
        cout<<endl;
    }
}

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

内存限制：128 MB时间限制：1.000 S

评测方式：文本比较命题人：2011014323

提交：2612解决：1758

返回比赛提交提交记录侧边提交

题目描述

有3种方法可以求解字符串模式匹配问题，分别是朴素的暴力算法、KMP算法和改进的KMP算法。
本题要求同学们编程实现这3种算法，并给出每种算法的字符比较次数，直观感受三种方法的执行效率。
本题为附加代码模式，main函数会自动附加在同学们提交的代码后面。main函数代码如下：

int main(){

// char S[]="ababcabcac",T[]="abcac",T2[]=" ababc";

// char S[]="aaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaaaaaaab",T[]="aaaaaaaaab",T2[]=" aaaab";

// freopen("1.txt","r",stdin);

char S[max], T[max];

while(cin >> S >> T){

cout<<S<<endl;

cout<<T<<endl;

cout<<"the length of S and T is " << strlen(S) << " and " << strlen(T) << endl;

int pos = findPos(S,T);

cout<<"findPos:"<<pos<<endl;

cout<<endl;

int next[strlen(T)];

CalcNext(T,next);

cout<<"next array is:";

for(int i=0;i<strlen(T);i++){

cout<<next[i]<<" ";

}

cout<<endl;

pos=findPos_kmp(S,T,next);

cout<<"findPos_kmp:"<<pos<<endl;

cout<<endl;

int nextVal[strlen(T)+1];

CalcNextVal(T,next,nextVal);

cout<<"nextVal array is:";

for(int i=1;i<strlen(T);i++){

cout<<nextVal[i]<<" ";

}

cout<<endl;

pos=findPos_kmp(S,T,nextVal);

cout<<"findPos_improved_kmp:"<<pos<<endl;

cout<<endl;

}

return 0;

}

输入

输入包括多组数据，每组数据为一行，包含由空格分隔的两个字符串，每个字符串仅由英文小写字母组成且长度不大于100。

输出

按照样例格式和给定的main函数代码输出执行结果，直观感受三种算法的执行效率。

样例输入复制

aaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaaaaaaab aaaaaaaaab

样例输出复制

aaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaaaaaaab
aaaaaaaaab
the length of S and T is 53 and 10
count in findPos is:155
findPos:-1

next array is:-1 0 1 2 3 4 5 6 7 8 

count in findPos_kmp is:106
findPos_kmp:-1

nextVal array is:-1 -1 -1 -1 -1 -1 -1 -1 8 

count in findPos_kmp is:65
findPos_improved_kmp:-1

提示

代码框架如下所示，请同学们补全代码后提交

#include <iostream>

#include <cstring>

#define max 200

using namespace std;

// brute force algorithm

int findPos(char S[], char T[]){

int count=0;

int sn = strlen(S), tn = strlen(T);

int i=0,j=0;

while(i<sn && j<tn){

count++;

/* write your code */

}

cout<<"count in findPos is:"<<count<<endl;

if(j>=tn) /* write your code */;

else /* write your code */;

}

// calculate the next array for KMP algorithm

void CalcNext(char T[],int next[]){

/* write your code */

}

// calculate the nextVal array for improved KMP algorithm

void CalcNextVal(char T[],int next[],int nextVal[]){

/* write your code */

}

// using KMP algorithm to find the position of T in S

int findPos_kmp(char S[], char T[], int next[]){

int count=0;

int sn = strlen(S), tn = strlen(T);

int i=0,j=0;

while(i<sn && j<tn){

count++;

if(/* write your code */){

/* write your code */

}else{

/* write your code */

}

cout<<"count in findPos_kmp is:"<<count<<endl;

if(j>=tn) /* write your code */;

else /* write your code */;

}

int main(){

// char S[]="ababcabcac",T[]="abcac",T2[]=" ababc";

// char S[]="aaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaabaaaaaaaab",T[]="aaaaaaaaab",T2[]=" aaaab";

// freopen("1.txt","r",stdin);

char S[max], T[max];

while(cin >> S >> T){

cout<<S<<endl;

cout<<T<<endl;

cout<<"the length of S and T is " << strlen(S) << " and " << strlen(T) << endl;

int pos = findPos(S,T);

cout<<"findPos:"<<pos<<endl;

cout<<endl;

int next[strlen(T)];

CalcNext(T,next);

cout<<"next array is:";

for(int i=0;i<strlen(T);i++){

cout<<next[i]<<" ";

}

cout<<endl;

pos=findPos_kmp(S,T,next);

cout<<"findPos_kmp:"<<pos<<endl;

cout<<endl;

int nextVal[strlen(T)+1];

CalcNextVal(T,next,nextVal);

cout<<"nextVal array is:";

for(int i=1;i<strlen(T);i++){

cout<<nextVal[i]<<" ";

}

cout<<endl;

pos=findPos_kmp(S,T,nextVal);

cout<<"findPos_improved_kmp:"<<pos<<endl;

cout<<endl;

}

return 0;

}

#include<bits/stdc++.h>
using namespace std;
#define max 300
 
int findPos(char S[],char T[])
{
    int count = 0;
    int sn = strlen(S);
    int tn = strlen(T);
    int index=-1;
    for(int i=0;i<sn;i++)
    {
        count++;
        if(S[i]==T[0])
        {
            int temp=i+1;
            int j=1;
            while(1)
            {
                if(temp==sn)
                break;
                if(j==tn)
                break;
                count++;
                if(S[temp]==T[j])
                {
                    temp++;
                    j++;
                }
                else
                break;
            }
            if(j==tn)
            {
                index=i;
                break;
            }
            if(temp==sn)
            break;
        }
    }
    cout<<"count in findPos is:"<<count<<endl;
    return index;
     
}
 
int findPos_kmp(char S[],char T[],int next[])
{
    int count = 0;
    int sn=strlen(S);
    int tn=strlen(T);
    int i=0,j=0;
    while(i<sn && j<tn)
    {
        count++;
        if(j==-1||S[i]==T[j])
        {
            i++;
            j++;
        }
        else
        {
            j=next[j];
        }
    }
    cout<<"count in findPos_kmp is:"<<count<<endl;
    if(j==tn)
    return i-j;
    else
    return -1;
}
 
void CalcNext(char t[],int next[])
{
    int length=strlen(t);
    next[0]=-1;
    int i=0,j=-1;
    while(i<length)
    {
        if(j==-1||t[i]==t[j])
        next[++i]=++j;
        else
        {
            j=next[j];
        }
         
    }
}
 
void CalcNextVal(char T[],int next[],int nextVal[])
{
    int tn=strlen(T);
    nextVal[0]=-1;
    for(int i=1;i<tn;i++)
    {
        if(T[i]==T[next[i]])
        nextVal[i]=nextVal[next[i]];
        else
        nextVal[i]=next[i];
    }
}
 
/*int main()
{
    char S[max],T[max];
    while(cin>>S>>T)
    {
        cout<<S<<endl;
        cout<<T<<endl;
        cout<<"the length of S and T is "<<strlen(S)<<" and "<<strlen(T)<<endl;
 
        int pos= findPos(S,T);
        cout<<"findPos:"<<pos<<endl;
        cout<<endl;
 
        int next[strlen(T)];
        CalcNext(T,next);
        cout<<"next array is:";
        for(int i=0;i<strlen(T);i++)
        cout<<next[i]<<" ";
        cout<<endl<<endl;
 
        pos = findPos_kmp(S,T,next);
        cout<<"findPos_kmp:"<<pos<<endl<<endl;
 
        int nextVal[strlen(T)+1];
        CalcNextVal(T,next,nextVal);
        cout<<"nextVal array is:";
        for(int i=0;i<strlen(T);i++)
        cout<<nextVal[i]<<" ";
        cout<<endl<<endl;
 
        pos=findPos_kmp(S,T,nextVal);
        cout<<"findPos_improved_kmp:"<<pos<<endl<<endl;
 
    }
    return 0;
}*/