设计一个算法，在串 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 算法了
网友评论