字符串学习笔记(8) 后缀数组

嗯，后缀数组听起来很奇特，但最终，它们实际上是处理字符串的强大工具。
我遇到的陷阱是，当我第一次开始研究这个问题时，它似乎有点复杂，但随着时间的推移，我已经学会了理解它。

例如，后缀数组用于对字符串的所有后缀进行排序，这对于搜索和比较等操作很有用。
例如，字符串“banana”有多个后缀，例如“banana”和“anana”，按字典顺序排序时，结果为“a”、“ana”、“anana”、“banana”和“nana”。
“那”。

这种排序的信息非常有用，例如快速计算两个后缀之间的最长公共前缀（LCP）。
该 LCP 对于许多弦乐问题都很重要。

举个例子，假设你有两个已排序的后缀，‘aabc’和‘aabce’，它们的LCP是‘aab’，长度为4
至于后缀数组的实现，代码看上去相当复杂，但不得不承认，这确实是构建后缀数组的重要一步。
涉及到的算法很多，比如如何高效排序、搜索等。

再比如，使用后缀数组来计算字符串的不相似子串的个数，实际上就是使用后缀数组和高度数组来计算不相似子串的个数。
这是一个巧妙的技巧。

最后，后缀序列也广泛用于解决实际问题，例如文本编辑器中的搜索和替换以及DNA序列分析中查找重复序列片段。

无论如何，这取决于你。
如果您对后缀数组感兴趣，请进一步研究。
这还是很有挑战性的。
我还在思考怎样才能更好地理解这个问题。

为什么不能对1.整个字符数组一次赋值或者2.整个数组整体赋值？

嗯……在C语言中，这个不得不说。

数组一旦定义，就是固定的。
类型和长度都是固定的。
它不是指针，不能像指针一样改变。
所以你写成inta[1 0], b[1 0];然后直接想a = b;这是行不通的。
编译器会骂你的。

看看其他语言，Java、C、JavaScript、Python，在这些语言中，数组就是对象。
对于对象来说，如果执行a = b;，a就会指向b之前的对象，b原来的对象就可以被回收。
a和b代表同一个数组。
简单的。

在C语言中，数组不是对象。
这只是记忆的一部分。
该内存有类型和长度。
就那么大一块。
不提供此类高级操作。
从逻辑上来说，你可以考虑一下。
是否可以将数组赋值改为为数组中的每个元素一一赋值？例如a[0] = b[0], a[1 ] = b[1 ]...这样。
嗯。
如果a比b长，余数不变吗？如果b比a长，b的余数怎么办？预订的？还是不算？有歧义。

更复杂的是，有关数组长度的信息只有在它成为指针之前才有用。
如果将其作为参数传递给函数或将其赋值给指针变量，如 int p = a;这次，数组 a 将退化为指针，并且长度信息将丢失。
指针赋值有其自己的一套规则。
您不能只将指向 int 的指针分配给指向 double 的指针。
当你把一个数组赋值给一个指针时，就相当于传递了这块内存的地址，长度就丢失了。

你想创建 a = b;这样两者共享同一块内存，并保留各自长度的信息来控制哪个更大、哪个更小……这与C语言“简单直接”、“底线”的设计理念相矛盾。
C语言希望你知道内存的数量、内存的类型，并手动管理这些。
因此，它不支持数组赋值a=b;。
太复杂了。

c++如何定义一个字符数组

老实说，我很难学习如何教授 C++ 字符数组。
你的笔记很详细，但如果我是学生我可能会有点困惑，因为知识点太密集了。

例如，在初始化部分，您提到了像 chargreeting[6 ]={...} 这样的显式初始化，这实际上是一个好习惯。
我记得第一次使用的时候，直接写了charhello[]="Hello";。
结果编译器傻眼了，因为它以为我忘记手动加上“\0”了。
仅当我将数组大小更改为 7 （“Hello\0”）时。
学生需要记住这个细节：当用字符串文字初始化时，终止符的位置必须保持不变。

操作部分的strcpy。
我在Linux上编写网络协议代码时，直接使用strcpy(arr1 , arr2 )，导致多次崩溃。
后来我了解到，没有终止符的字符串将被读取超出范围。
这必须在黑板上清楚地解释。
最好结合内存地址图来画。
您提供的 strcat(arr1 ,arr2 ) 拼接示例非常好。
不过最好补充一下，arr1 空间不够的时候会溢出。
因此，使用前必须检查。

std::string 部分实际上可以再次突出显示。
我有一个学生使用 std::string 作为常规数组。
结果，析构函数没有被正确调整，内存从未被释放。
相比之下，字符数组就像C语言中的指针。
您必须手写“\0”。
std::string 就像一个具有自动垃圾回收功能的智能指针，它知道“\0”是什么时候。

最重要的是安全。
您提到的 cin.getline 是一个很好的建议。
我写学生管理系统的时候，用cin>>直接读取名字。
于是，“张三丰”就分裂成了“张”和“三丰”。
我花了很长时间才弄清楚。
让我们举一个小例子：假设用户输入“1 2 3 4 ABCD”并使用 cin.getline(buffer, 6 ) 捕获“1 2 3 4 ”，而“ABCD”仍保留在输入缓冲区中。
下次再用cin.getline读入时，程序就会爆炸。
因此，需要教导学生 std::cin.ignore(std::numeric_limits::max(), '\n') 首先清除缓冲区。

这个知识点需要反复练习。
我在帮同事排查字符串溢出问题，花了两个小时才看到gdb中“\0”后面出现一堆乱码。
因此，学生最好写一个简单的实验：用strcpy将“Hello”复制到一个大小为5 的数组中，然后打印出来，看看“\0”之前是什么。
这样的具体场景，比只讲概念要有效得多。