C++ / C#简单界面求字符串的前缀、后缀、不与前后缀重复的子串

C++ / C#简单界面求字符串的前缀、后缀、不与前后缀重复的子串

【写在前面：首先，我是个菜鸡，没认真学多久的C++，被迫自学了半个小时C# winform界面设计，而且是第一次写博客。其次，这个程序里面并没用什么高端大气上档次的算法，就是一些基础，没有类(class)啊什么的，只有一些函数，有一些方法确实是很笨，但是好歹是我想出来的，自我感觉还是很好理解的，吧。代码在下面的链接里下载，不想看我叭叭的就直接下代码】
C++实现：
C#实现：
【百度云地址】（不知道为啥，我上传的东西总是自动要积分，不能免费下载）

提取码：1be1

程序功能及例子介绍

1. 输入：一个串x；
2. 输出：前缀的集合、后缀的集合、除前后缀之外所有的子串；
3. 例子：x=“abcd” 则:
   x的前缀={a, ab, abc, abcd, 空串}
   x的后缀={d, cd, bcd, abcd, 空串}
   x的子串={a, ab, abc, abcd, b, bc, bcd, c, cd, d, 空串}
   x去除与前后缀重合的元素之后的子串={b, bc, c}；
4. 解释：前缀即从字符串的第一个字符开始每次往后多取一个字符再加上空串，后缀即从字符串的最后一个字符开始每次往前多取一个字符再加上空串，子串即该字符串的前缀与每次去掉第一个字符后所得新字符串的前缀的并集。
   

   目录

   • • 程序功能及例子介绍
   • C++实现(无界面)
   • • 算法设计思路(非完整代码)
     • • • • 1. 求前缀(后缀类似)
           • 2. 求子串并删去与前后缀重合的部分
           • 3. 判断字符串是否在要求的两个数组里
           • 4. 去除数组中重复的元素
           • 5. 前缀输出显示(其他类似)
   • C#实现(简单界面 winform)
   • • 部分功能(算法)实现原理(非完整代码)
     • • • • 1. 界面设计和基本操作
           • 2. 去除子串中与前后缀元素相同的元素(去除一个数组中与另一个数组相同的元素)
           • 3. 实现输入完成后按下Enter即开始解析(相当于点击解析按钮)
           • 4.前缀输出显示(其他类似)

C++实现(无界面)

C++运行结果：

算法设计思路(非完整代码)

这里我会把这里面用到的一些算法(姑且算得上算法吧)的原理和我怎么想的解释一下，如果看的话一定要看注释！！。

1. 求前缀(后缀类似)

string* prefix(string str)
{int len = str.length();  //获取字符串的长度string s = "";  //定义变量来存储每个元素string* result = new string[len];  //定义数组来存放前缀的元素们for (int i = 0; i < len; i++) {s = s + str[i];  //每个元素都是上一个元素往后再加一个字符result[i] = s;  //将元素存放进准备好的数组容器中}return result;  //返回结果数组
}

• 其中，直接定义string类型的字符串，就不用char来一个字符一个字符的加了，而对于字符串类型，若string str=“abc”，那么str[0]=‘a’，str[1]=‘b’，str[2]=‘c’；
• 前缀的元素个数就是要求的字符串的长度加1(空串)，而空串我选择在输出的时候在末尾直接加上，所以数组里面存放的元素个数就是字符串str的长度，例：str=“abc", result={a, ab, abc, abcd}；
• 而求后缀即是”从最后一个元素开始，每个元素都是上一个元素往前再加一个字符“，即for循环要从len-1开始逐渐减小到0，从后往前加字符即s=str[i]+s 。

2. 求子串并删去与前后缀重合的部分

int max_res_index = ((1 + len)*len) / 2;  //获取总长度
string* result_son = new string[max_res_index];  //存放子串的数组
int res_index = 0;  //子串数组的下标
for (int i = 0; i < len; i++) {  //每次删除最前面的字符并求前缀，直到没有字符string* temp = prefix(str);  //用temp存放每一次的前缀for (int j = 0; j < len - i; j++) {//对于每一个元素，都判断其是否在前缀或后缀数组中，若在，则不将它存放进子串数组中if (if_in_it(temp[j], result_pre, result_suf, len)) continue;  //执行continue，不继续执行下面的所有代码，直接跳到for循环中的j++来执行result_son[res_index] = temp[j];res_index++;  //每存放一个元素，下标都加一}ase(str.begin());  //删去字符串的第一个字符delete[] temp;  //一定记得释放内存，因为temp是调用了函数里new出来的值
}

• 其中，子串的最大长度，去掉空串的话，就是1到len的累加，例如(下面所说的前缀子串均没算空串) str=“abcd”，长度为4，其前缀有4个，”bcd“前缀3个，以此类推，则str的子串有4+3+2+1个，由此可得子串的最大长度应为((1+len)*len)/2 ；
• 函数if_in_it()中传递的参数result_pre和result_suf分别是字符串的前缀和后缀。
• 注意，res_index从0开始，每存放完一个数据之后加一，则当存放完result_son[4]后，res_index++，此时res_index=5，即为result_son中已经存放的元素个数，而并非为最后一个元素的下标。
• 一定要记得释放内存！！！！而且在整个程序结束后，要把result_pre和result_suf和result_son的内存都释放掉

3. 判断字符串是否在要求的两个数组里

bool if_in_it(string temp_s, string* r1, string* r2, int len)
{for (int i = 0; i < len; i++) {  //遍历两个数组r1、r2//如果该元素与两数组中任意一个元素相同，返回true，表明该元素至少在其中一个数组中if (temp_s == r1[i] || temp_s == r2[i])return true;}return false;  //若遍历完成后均不返回值，则返回false，表明元素不在两数组中
}

• 其中，如果传递更多参数，还能判断该元素是否在更多数组中；
• 若两数组长度不同，则分别遍历，不然会导致溢出或不完全遍历。

4. 去除数组中重复的元素

for (int i = 0; i < res_index; i++)
{for (int j = i + 1; j < res_index; j++) {if (result_son[i] == result_son[j]) {  //如果后面有元素与当前元素相同for (int k = j + 1; k < res_index; k++) {result_son[k - 1] = result_son[k];  //用j后面的元素将该元素进行覆盖}res_index--;  //下标减一j--;  //原来重复的位置被新的元素替代了，所以要使用同一个下标继续}}
}

• 其中，res_index是上一步的时候存放完之后的下标，所以此时子串数组中有用的数据长度即为res_index ；
• 最外层循环的i是用以从第一个元素开始取，第二层循环从i之后的元素开始遍历，判断i之后的元素有没有和i处元素相同的，若有，则利用内层循环，将后面的元素把前面的元素依次覆盖，再将数组总下标数减一，表现出来的效果为，在数组中，相同元素较后的那个会被覆盖，位置在前的则保留；
• 注意，覆盖之后将下标减一是人为的让人无法访问后面的元素，但是元素仍旧存在，例如result={1，2，3，4，3，5，4，6} res_index=8，去重后result={1，2，3，4，5，6，6，6} res_index=6

5. 前缀输出显示(其他类似)

string* result_pre = prefix(str);  //获得前缀
cout << "X的前缀 = { ";
for (int i = 0; i < len; i++) {cout << result_pre[i] << ", ";  //遍历输出
}
cout << "空串 }n";  //结尾加上空串

• X=“abcd”
  输出示例：
  X的前缀 = { a, ab, abc, abcd, 空串 }

C#实现(简单界面 winform)

C#程序运行结果：

部分功能(算法)实现原理(非完整代码)

winform我也是只学了半个小时，只知道一些必要的工具的简单使用方法，我的原则是能用就行，核心代码和C++的差不多，但是“去除与前后缀相同的元素”这部分，我讲了另一种算法(我提供的C++源码里面也有)。

1. 界面设计和基本操作

• 用Visual studio 创建一个C# WinForm(C# Windows窗体应用程序)，如下图：

• 创建之后就有一个窗口，点击左侧的工具箱就能看到很多组件，把需要使用的东西拖进去就行了，组件使用介绍如下图：
  

• Lable在这里用来注释，做标记用的
  ListBox在这里用来以行输出显示结果
  Button在这里有两个，一个用来运行程序，一个用来退出程序
  TextBox在这里用来接收用户输入的字符串。

• 然后单击(强调单击)你拖进去的组件，你就能在红框框里看见这个组件的属性，如果没有，那就点进紫色框框“重置窗口布局”就有了，属性里面有一项叫做(Name)，指的是这个控件的ID，如下图：

• 一般Button控件默认ID为button1，button2，TextBox控件默认ID为textBox1…以此类推，这里我改了一下，TextBox的Name改成了text_input，ListBox的Name改成了result，解析Button的Name改成了OK，退出Button的Name改成了EXIT。

• 首先双击退出按钮，进入该按钮的Click函数体里面，顾名思义，这个函数就是点击按钮之后要执行的函数，点击退出按钮当然是为了退出，所以在里面写上如下代码：

this.Close();  //用以关闭整个窗口

• 然后双击解析按钮，同样进入其Click函数体，里面的代码即是点击解析按钮所要执行的，在其中写上如下代码，即可实现“点击按钮后，将用户输入的数据显示在ListBox中”这样的功能。

string str = text_input.Text;  //获取用户在TextBox中输入的串
int len = text_input.Text.Length;  //获取输入串的长度
string output_str = "串X = " + str;  //‘+’是重载，用于直接连接两个string类型的数据
result.Items.Add(output_str);  //把output_str的内容附加到listbox中，每次都另起一行

2. 去除子串中与前后缀元素相同的元素(去除一个数组中与另一个数组相同的元素)

private void extra(ref string[] res, string[] strs, ref int max_res, int max_strs) 
{   //ref用于直接引用值，改变变量的同时也修改值，我认为相当于C++中的&for (int i = 0; i < max_res; i++) {  //遍历需要去除元素的数组for (int j = 0; j < max_strs; j++) {  //遍历需去除元素的来源数组if (i == max_res)  break;  //如果遍历已经到达尾部，直接退出循环if (res[i] == strs[j]) {  //判断数组res中的元素与strs中的元素是否相同for (int k = i + 1; k < max_res; k++) {res[k - 1] = res[k];  //用其后面的值将其覆盖达到删除的作用}max_res--;j = -1;  //为了让j再次从0开始}}}
}

• 假设：strs={b, d}，max_strs=2 res={a, b, b, c, d} ,max_res=5

• 上表中的res[i]取的都是上一步骤中所获得的的res数组中的数据
• 【这一部分用python写真的相当简单，有兴趣的可以去试试。】

3. 实现输入完成后按下Enter即开始解析(相当于点击解析按钮)

private void text_input_KeyPress(object sender, KeyPressEventArgs e)
{if (e.KeyChar == 'r')  //实现按下Enter键执行按钮OK的功能OK.PerformClick();
}

• 其中，函数名text_input是我的TextBox组件的Name，单击TextBox组件，在属性框里面点击小闪电图标(事件)，在里面找到KeyPress事件，双击就可以进入函数体_KeyPress内进行编辑了。

4.前缀输出显示(其他类似)

//输出前缀及个数
string[] result_pre = prefix(str);
string output_pre = "X的前缀 = { ";  //定义一个用来整理结果的字符串
for(int i=0;i<len;i++) {output_pre = output_pre + result_pre[i] + ", ";  //把前缀元素一个一个连接在output字符串尾部
}
output_pre = output_pre + "空串 }   个数 = " + (len + 1);  //最后自主加上空串，顺便输出一下个数
result.Items.Add(output_pre);  //将整理好的结果加在ListBox的末尾显示

• 关于个数，因为加了空串，所以个数要加一
• 例X=“abcd”
  输出示例：X的前缀 = { a, ab, abc, abcd, 空串 } 个数 = 5

【由于本人学艺不精，C++少了释放内存的部分，一定记得加上，new和delete一定配套使用！而C#好像不用释放，具体我也不晓得】
【写在最后：程序代码在最前面的链接里面，没看到的仔细看一下。
我确实是学的不多也学的不精，这篇文章是纯原创，第一次写博客也是就像是把实验报告细化之后写了上来，有很多不足之处也希望批评改正，同时，有什么问题也可以和我讨论，毕竟这都是照着我的思路来写的，可能会有看不懂的地方。】