[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

上机助教：你们这个怎么讲的？我们当时讲了两节课。

答：大概就是……讲了半节课，老师最后说这个很重要，我们就自己回去看咯。

上机助教：……这个是很重要，你们好好学啊。：）

需求描述

原则上的需求：

循环读入字符
查找最后一次出现的位置：每查找到一次记录，输出最后一个查找到的位置

我一拍脑瓜实现的需求：
string 类及基本操作
朴素匹配算法及 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);

};

比较函数是比较 s1 和 s2，相同返回 0，s1 > s2 返回 1，s1 < s2 返回 -1
赋值= 、下标[ ]、调用( )、和成员访问箭头->、取地址&、引用*，这些运算符因为必须跟在给定类型之后，所以必须是成员函数
输入>>输出<<运算符跟在 istream 和 ostream 后，所以必须是友元函数
复合赋值运算符应该是成员（如+=），但是并非必须
其它运算符如果是对称性的运算符（可能转换任一端的运算对象，例如算数、相等性、关系和位运算符等）通常定义为友元函数。如果把 + 运算符定义成一个成员函数，则它左侧和右侧的运算对象的类必须和运算符同类。（即我定义的 + 运算符无法计算 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 算法了

前置技能
- 字符串
- KMP 算法
需求描述
概要设计
具体实现

巴特西