CS144-1

CS144-1

前言
cmake --build build --target check 0来检查你的lab0后就可以开始这部分的实验了
事实上对于这部分实验，在我整个实验中花费的时间是最长的，代码也是最长的，而且即使通过了，后续的实验中，也会由于这部分导致超时，而无法通过。所以参考了其他大佬的思路才通过了这部分的测试

这是我参考的大佬的链接，需要代码的可以去他那边看看https://github.com/Mobuiss

目前大多数对于这一题的思路就是重复子串的合并，我一开始想到的也是用map来实现这个过程，但是后面写得也很长，性能很低。大佬的思路就不一样了，是用一个vector来维护buffer，下面详细讲。

实验开始
这个实验的主体是通过insert这个函数实现的

它的传参有

uint64_t first_index string data bool is_last_substring Writer& output

first_index是每一个data绝对位置，也就是类似于leetcode中合并区间的区间下标。data就是数据本身，可以调用.size来获取长度，is_last_substring就是问是否是最后一个数据段,output是一个输出接口，调用output.push（）就可以把完整的数据段输出。

实现过程：

先是看是否是最后一段数据，如果是就设置保存一下，后面可以用来作为结束的依据。

然后就是判断是否是过于新或者过于旧的片段我们就不要

如果是旧消息（原作者意思是设置左边界）或者新消息（原作者是设置右边界）我们就截取窗口位置
他在实现右边界是比较有意思的，由于之前排除掉就消息，只剩下刚刚好符合的消息，和新消息，通过min函数来判断是否符合容量去实现的。也就是新消息和刚好落在窗口内的消息一起判断了
后面的思路也是让让拍案叫绝，是通过一个vector来维护一串数字，这些数字可以转换成char类型，把符合条件的消息全部转换成int放到vecotr中，然后通过一个随机固定的数字val填充为填充的，原作者用的值，咳咳(笑而不语)。然后如果需要的下标不是val的值（也就是恰好等于我们的需要的下标）则把其后面连续的都放到buffer中
具体实现可以去看原作者是如何做的，接下来我讲另一种思路 也就是我一开始想做的，也是绝大多数人的思路 经历和上面一样的筛选步骤后 存入后由于map会自动排序，会形成如下（实际上维护可能只有两到三个左右的消息段，这里为了演示画多一点）
然后会通过辅助函数来将所有的片段拍在一起，其中涉及到左合并和右合并

然后回放到map中（图中有可能结果有多个不相邻的判断，不一定是只有一个），下次放入判断前重新检查一下是否有新的片段成为了需要的下标，就推送到output里

由于笔者写的这部分代码确实不太好，所以如果想参考的话可以去我上面推荐的作者或者其他博客看看。