[C++] 习题 2.18 倒序查找字串

设计一个算法，在串 str 中查找字串 substr 最后一次出现的位置（不能使用 STL）

为了完成那个不能使用STL，我实现了 string 类及 KMP 算法……但是现在回想一下当时难道是傻了？完全没有必要啊 orz （所以说这一整篇要讲的其实是 string 类的实现和 KMP 算法）。

前置技能

• 字符串
  本质上是字符数组，以'\0'标记结束，所以它每一位的单个元素都是可以提取的，如s = “ abcdefghij ”，则s[0]为a，s[9] 为j。
  通常以串的整体作为操作对象，如：在串中查找某个子串、求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。
  两个字符串相等的充要条件是：长度相等，并且各个对应位置上的字符都相等。
  设T、P是两个串，求P在T中首次出现的位置的运算叫做模式匹配，其中，T为目标串(target)，P为模式串(pattern)。

• KMP 算法
  朴素模式匹配算法是一位一位地进行比较，使用循环嵌套，最坏情况需要进行目标串长度×模式串长度次比较，所以效率较慢。此时，Knuth、Morris、Pratt三人不满足于目前的匹配效率，对模式匹配进行深入研究，发现了在进行模式匹配的时候可以有更快速的方法，即基于模式串本身算出特征向量，增加每次不匹配时右移模式串位数，于是他们对朴素模式匹配算法进行了改进，改进后的算法叫做 KMP 算法。
  首先，我们书上有关 KMP 算法的那部分可读性不高。那么在网上搜索之后发现，网上有关 KMP 算法的文章很多，但详细讲述过程及原理的不多，真正讲得好的文章在定义方面又有细微的不同，比如说有些从1开始标号，有些next表示的是前一个而有些是当前的，通读下来，难免会混乱。
  所以我推荐一篇包含以上为读者着想的内容，有约法两条；包含以下图片，可读性很强的一篇博文：https://www.cnblogs.com/SYCstudio/p/7194315.html
  

  SYCstudio - KMP
  上机助教：你们这个怎么讲的？我们当时讲了两节课。
  答：大概就是……讲了半节课，老师最后说这个很重要，我们就自己回去看咯。
  上机助教：……这个是很重要，你们好好学啊。：）

需求描述

原则上的需求：
1 ) 循环读入字符
2 ) 查找最后一次出现的位置：每查找到一次记录，输出最后一个查找到的位置
我一拍脑瓜实现的需求：
1 ) string 类及基本操作
2 ) 朴素匹配算法及 KMP 算法
果然当时是傻了

概要设计

头文件基本引用书上的内容（并不，发现书上的函数有些是多余的，另外缺少对某些运算符的重载），实现过程中发现 string 与命名空间 std 中已有关键字重复，所以使用了 String 作为类名。（在参考了书上和网上的代码之后，我总结出）基本思想是实现好对字符数组的操作，剩下对字符串的操作就各种调用 strcpy 和 strcat，真省事……啊？（感觉很奇怪23333）

#include<iostream>

class String
{
private:
    char * str;
    int size;
    char * strcpy(char * s1,const char * s2);    //将s2复制到s1,并返回s1
    char * strcat(char * s1,const char * s2);    //将s2拼接到s1尾部
public:
    String();
    String(char * s);              //构造函数
    String(const String & s);      //拷贝构造函数
    ~String();                     //析构函数
    int strsize();                 //返回字符串长度 
    int strlen(char * s);          //计算长度，不计结束符，空串长度为0
    int strcmp(const char * s1,const char *s2); //比较s1和s2
    String subString(int index, int count);     //提取字串，当长度非法时返回自身
//  char * strchr(char * s,char c);             //查找s中c出现位置，s不含c则返回空指针
//  char * strrchr(char * s,char c);            //从s尾部查找c的位置，不含则返回空指针
    bool operator == (const String &s);
    String & operator = (const String & s);
    String & operator += (String & s);
    String operator + (String & s);
    char operator [](int index);
    friend std::ostream & operator << (std::ostream & o,String & a);
    friend std::istream & operator >> (std::istream & is,String & a);
};

1 ) 比较函数是比较 s1 和 s2，相同返回 0，s1 > s2 返回 1，s1 < s2 返回 -1
2 ) 赋值= 、下标[ ]、调用( )、和成员访问箭头->、取地址&、引用*，这些运算符因为必须跟在给定类型之后，所以必须是成员函数
3 ) 输入>>输出<<运算符跟在 istream 和 ostream 后，所以必须是友元函数
4 ) 复合赋值运算符应该是成员（如+=），但是并非必须
5 ) 其它运算符如果是对称性的运算符（可能转换任一端的运算对象，例如算数、相等性、关系和位运算符等）通常定义为友元函数。如果把 + 运算符定义成一个成员函数，则它左侧和右侧的运算对象的类必须和运算符同类。（即我定义的 + 运算符无法计算 char* 类型在左，和 string 类型的相加）
看到没这个类里明明有前后查找，为什么我不但不实现还要再定义一个头文件实现三种查找？典型的反面教材啊/捂脸

#include"string.h"

int NaiveStrMatching(String & T,String & P);     //朴素字符串模式匹配算法
int * Next(String & s);                          //计算特征向量
int KMPStrMatching(String & T,String & P);       //KMP匹配算法
int tKMPStrMatching(String & T,String & P);      //调用KMP进行反向查找

T为目标串 ( target ) P为模式串 ( pattern )

具体实现

string.cpp
抄好书上的代码之后疯狂 debug，感受就是delete[]是个学问

#include "string.h"
#include<iostream>

String::String(){
    size = 0;
    str = nullptr;
}
String::String(char * s){
    size = strlen(s);
    str = new char[size + 1];
    strcpy(str,s);
}
String::String(const String &s){
    size = s.size;
    strcpy(str,s.str);
}
String::~String(){
    size = 0;
    delete [] str;
}
int String::strsize(){
    return size;
}
int String::strlen(char * s){
    int count = 0;
    while(s[count] != '\0') count++;
    return count;
}

int Sring::strcmp(const char * s1,const char *s2){
    int count = 0;
    while(s1[count] != '\0' && s2[count] != '\0'){
        if(s1[count] > s2[count])       return 1;
        else if(s1[count] < s2[count])  return -1;
        count++;
    }
    if(s1[count] == '\0' && s2[count] != '\0')          return -1;
    else if(s1[count] != '\0' && s2[count] == '\0')     return 1;
    else                                                return 0;
}
char * String::strcpy(char * s1,const char * s2){
    int i = 0;
    while(s2[i] != '\0'){
        s1[i] = s2[i];
        i++;
    }
    s1[i]='\0';
    return s1;
}
char * String::strcat(char* s1, const char* s2){
    int i = 0,j;
    j=strlen(s1);
    do{
        s1[j] = s2[i];
        i++;
        j++;
    }while(s2[i] != '\0');
    return s1;
}
String String::subString(int index, int count){
    String temp;
    if(index >= size || count == 0){
        temp.size = size;
        temp.str = str;
        return temp;
    }
    int i;
    if(count > size - index)
        count = size - index;
    char *q;
    temp.str = new char[count + 1];
    q = &str[index];
    for(i = 0; i < count; i++)
        temp.str[i] = * q++;
    temp.str[i] = '\0';
    temp.size = count;
    return temp;
}
bool String::operator == (const String &s)
{
    return strcmp(str,s.str) ? false : true;
}
String & String::operator = (const String & s){
    if(size != s.size){
        if (size != 0) delete [] str;
        str = new char[s.size+1];
        size = s.size;
    }
    strcpy(str,s.str);
    return * this;
}
String String::operator + (String & s){
    String tmp(str);
    delete [] tmp.str;
    tmp.str = new char[size + s.size + 1];
    tmp.size = size + s.size;
    strcpy(tmp.str,str);
    strcat(tmp.str,s.str);
    return tmp;
}
String & String::operator += (String & s){
    size = size + s.size;
    char *tmp = new char[size + 1];
    strcpy(tmp,str);
    strcat(tmp,s.str);
    delete [] str;
    str = tmp;
    return * this;
}
char String::operator[](int index){
    return str[index];
}

std::ostream & operator << (std::ostream &out,String &a) {
    if(a.size == 0)
        out<<"nullptr";
    else
        out<<a.str;
    return out;
}
std::istream & operator >> (std::istream &in,String &a){
    char tmp[1024]={0};
    in >> tmp;
    if(a.str != NULL){
        delete a.str;
    }
    a.size = a.strlen(tmp);
    a.str = new char[a.size+1];
    a.strcpy(a.str,tmp);
    return in;
}

strmatching.cpp
书上的 KMP 算法代码好像没什么问题，但实在是不知道他的下标怎么算得

#include"strmatching.h"
#include"string.h"

int NaiveStrMatching(String & T,String & P){
    int p = 0,t = 0;
    int plen = P.strsize();
    int tlen = T.strsize();
    if(tlen < plen)     return -1;
    while(p < plen && t < tlen){
        if(T[t] == P[p]){
            p++;
            t++;
        }
        else{
            t = t - p + 1;
            p = 0;
        }
    }
    if(p == plen) return (t - plen + 1);
    else return -1;
}
//此处计算特征向量的方法显然是我自己闭门造车的产物
//更好的算法详见上文中提到的博文
int * Next(String & s){
    int i, j;
    static int *F = new int[s.strsize()];
    F[0] = 0;
    for (i = 1;i < s.strsize();i++) {
        F[i] = 0;
        for (j = i;j > 0;j--){
            for(int k = 0;k <j;k++){
                if(s[k] != s[k + i - j + 1])
                    break;
                if(k + i - j + 1== i){
                    F[i]=j;
                    j=0;
                }
            }
        }
    }
    return F;
}
int KMPStrMatching(String & T,String & P){
    int p = 0,t = 0;
    int plen = P.strsize();
    int tlen = T.strsize();
    if(tlen < plen)     return -1;
    int *F = Next(P);
    while(p < plen && t < tlen){
        if(T[t] == P[p]){
            if (p == (plen -1))     return t-plen+2;
            p++;
            t++;
        }
        else{
            p = F[p-1];
            if(p == 0 && T[t] != P[p])  t++;
        }
    }
    return -1;
}
int tKMPStrMatching(String & T,String & P){
    int find,f;
    String F;
    find = KMPStrMatching(T,P);
    f = find;
    if (find == -1)
        return -1;
    F = T.subString(find + P.strsize() -1,1024);
    while(find != -1){
        find = KMPStrMatching(F,P);
        if(find != -1 && find + P.strsize() <= F.strsize()){
            f += find;
            f += P.strsize() - 1;
            F = F.subString(find + P.strsize() -1,1024);
        }
        else if(find != -1){
            f += find;
            f += P.strsize() - 1;
            return f;
        }
        else
            return f;
    }
    return -1;
}

main.cpp
封装好的类调用果然很方便……能实现的也远远不止这道题

#include"string.h"
#include"strmatching.h"
#include<iostream>

using namespace std;

int main(){
    String a,b;
    cout<<"please input a:"<<endl;
    cin>>a;
    cout<<"please input b:"<<endl;
    cin>>b;
    cout<<"a in b : "<<NaiveStrMatching(b,a)<<endl;
    cout<<"a in b : "<<KMPStrMatching(c,a)<<endl;
    cout<<"a in b : "<<tKMPStrMatching(c,a)<<endl;
}

用户的需求是3，如果在同样的时间内作出了5，大概是好事；如果用成倍的时间作出了10，大概就是傻子了吧。

唉。

就当复习 KMP 算法了