我有一个由很多行组成的文件，比如：
- 约翰晚上跑步
- 约翰晚上不走路
- 杰克晚上跑步
- 杰克在等人
- 约翰在等人
我需要编写一个程序，将类似的句子分组并打印到文件中。类似的句子是指它们之间只改变了一个单词的句子。
例如，输出文件应该看起来像：
- 约翰晚上跑步
- 杰克晚上跑步
变化的单词是：Jhon，Jack
- 杰克在等人
- 约翰在等人
变化的单词是：Jhon，Jack
我想通过解析文件来实现它，并将字符串按每个字符串中多个单词的组排列(所有有6个单词的字符串都将分组在一起，所有有5个单词的串都将分组一起，以此类推(
排列成组后，我可以将每个字符串拆分为一组单词，并将每个字符串与另一个字符串进行比较，然后检查是否匹配。
我认为我的解决方案效率不高。
有人能想出更好的解决方案吗？
让我们假设有M个句子，每个句子的平均单词数为N。对于每个句子，我们希望生成一个其他句子的索引列表(最多M-1(，这些句子只相差一个单词。因此，输入大小为O(MN(字，输出大小为O(M²(number。这里有一个在O(MN+M²(中运行的算法，因此是最优的。
首先，阅读所有的句子，将它们分成单词，并将单词编入哈希表中。因此，我们可以把句子想象成数组。为了帮助我们的思维过程，我们可以进一步将句子视为拉丁文小写字符串，将每个首词替换为字母(最多可以使用26个不同的单词(。
现在，我们希望能够查询O(1(中的每对字符串(A，B(，并询问">A和B相差一个字母吗？"？对于一个浏览器，
- 设l为A和B的公共长度
- 设p是A和B之间的公共前缀的长度
- 设s是A和B之间的公共后缀的长度
- 然后注意，如果l=p+s+1，则A和B仅相差一个字母
因此，我们的算法可以归结为在恒定时间内确定每对字符串的公共前缀和公共后缀的长度。我们展示了如何对前缀执行此操作。同样的方法适用于后缀，例如通过反转字符串。
首先，对字符串进行排序，并测量每个连续对之间的公共前缀。例如：
banana
> common prefix 3 ("ban")
band
> common prefix 4
bandit
> common prefix 1
brother
> common prefix 7
brotherly
> common prefix 0
car
现在，假设您想查询"band"one_answers"brothery"之间的通用前缀。这将是"band"one_answers"brothery"之间的最小数值，或min(4，1，7(=1。这可以在O(M(处理时间和O(1(每个查询中使用范围最小的查询来实现，尽管在O(M log M(预处理时间中可以使用更简单的实现。