实现字符串的数组存储报告

Question

用c++
1实现字符串的数组存储。

2实现串的朴素的匹配算法，找出子串位置

3编写改进型的串的匹配算法，指出改进在何处，时间复杂度和空间复杂度各是多少。

4叙述该部分每个板块需求

5在此说明每个部分的算法设计说明( 可以是描述算法的流程图)，每个程序中使用的存储结构设计说明(如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和成员函数原型声明)
6调试过程中的问题解决方式和改进设想

afsdasfda主串
das 子串

Answer 1

二、需求分析（格式：宋体，4号，加粗，两端对齐）
实现子串匹配
在该部分中叙述每个模块的功能要求
（正文格式：宋体，小4号，不加粗，两端对齐，1.5倍行距）
BF暴力匹配，KMP算法分为求next数组模块与子串匹配模块
三、概要设计（格式：宋体，4号，加粗，两端对齐）
在此说明每个部分的算法设计说明（可以是描述算法的流程图），每个程序中使用的存储结构设计说明（如果指定存储结构请写出该存储结构的定义，如果用面向对象的方法，应该给出类中成员变量和成员函数原型声明）。
（正文格式：宋体，小4号，不加粗，两端对齐，1.5倍行距）
算法使用回溯+双指针,BF算法不开辟额外数组存储，KMP算法要开辟一块与模式串等长的next数组记录回溯下标

四、详细设计（格式：宋体，4号，加粗，两端对齐）
各个算法实现的源程序（可以是一组源程序，每个功能模块采用不同的函数实现），源程序要按照写程序的规则来编写。要结构清晰，重点函数的重点变量，重点功能部分要加上清晰的程序注释。
（正文格式：宋体，小4号，不加粗，两端对齐，1.5倍行距）
#include<iostream>
#include<string>
#include<vector>
using namespace std;
int BF(string s, string t)//朴素算法，时间复杂度O(m-n+1)*n，空间复杂度O（1）,未使用额外数组空间
{
 int i = 0, j = 0;
 while (s[i] && t[j])//字符串都没走到'\0'
 {
  if (s[i] == t[j])//相等向后匹配
  {
   i++;
   j++;
  }
  else
  {
   i = i - j + 1;//回退
   j = 0;
  }
 }
 if (t[j])//如果匹配串还未走完，则无匹配子串
  return -1;
 else
  return i - j;
}


//改进，Kmp算法
vector<int>getnext(string t)//获取next数组
{
 int len = t.size();
 vector<int>next(len, 0);
 for (int i = 1, j = 0; i < len; i++)
 {
  while (j > 0 && t[i] != t[j])
   j = next[j - 1];//不匹配，模式串指针通过next数组回退
  if (t[i] == t[j])//相等，指针后移
   j++;
  next[i] = j;//记录回退位置
 }
 return next;
}
int KMP(string s, string t, vector<int>next)//KMP，时间复杂度O（m+n）,空间复杂度O（n）
{
 int lens = s.size(), lent = t.size();
 for (int i = 0, j = 0; i < lens; i++)
 {
  while (j > 0 && s[i] != t[j])
   j = next[j - 1];//不相等回退
  if (s[i] == t[j])
   j++;
  if (j == lent)//当模式串达到末尾时匹配成功
   return i - lent + 1;
 }
 return -1;
}
int main()
{
 string s = "afsdasfda", t = "das";
 cout << BF(s, t) << endl << KMP(s, t, getnext(t));
 return 0;
}
五、测试数据及其结果分析（格式：宋体，4号，加粗，两端对齐）
（正文格式：宋体，小4号，不加粗，两端对齐，1.5倍行距）
正确无误
六、调试过程中的问题（格式：宋体，4号，加粗，两端对齐）
每个模块设计和调试时存在问题的思考（问题是哪些？问题如何解决？），以及算法的改进设想。
尽可能降低时间复杂度，拿空间换时间，多观察数据之间的规律