目录

问题 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;
      }
}