从字符串数组中至少可以通过两种方式生成的最短字符串

Question

声明：

给定一个字符串数组S。你可以通过组合数组S中的元素来生成一个字符串(你可以多次使用一个元素)

在某些情况下，有很多方法可以从数组S中生成特定的字符串。

示例：

S＝｛a，ab，ba｝

然后有两种方法可以使字符串"；aba"：

• "a"+"ba">
• "ab〃+"a">

问题：

给定一个字符串S的数组。找到最短的字符串，这样就有不止一种方法可以从S中生成该字符串。如果没有，打印出-1。

p/S:我想了很多天，但这是迄今为止我得到的最好的一个：

• 生成数组的所有排列
• 对于每个排列，从数组S中生成一个字符串
• 检查该字符串是否是以前生成的，如果是，打印出该字符串，如果不是，保存该字符串

但是这个算法显然不能通过所有的测试用例。我想不出比这更好的算法了。

Answer 1

想象一下，你已经找到了你的字符串，并且你用两种不同的方式将它与来自S的字符串进行匹配。你从两个不同的匹配前缀的字符串开始，然后你重复地将一个来自S的串加到较短的字符串中，直到你得到匹配的长度。从你的例子来看，这就是

"ab"
"a"
"ab"
"aba"
"aba"
"aba"

在每一步中，都有两个不同于S的字符串，它们在末尾重叠。

想象一个有向图，其中每个顶点都是元组(i，j，t)，其中i和j是末尾重叠字符串的索引，而t则是重叠部分后较长字符串末尾剩余的字符数。使其成为t>=0并且字符串i始终是第一个结束的字符串。

图形的边表示可以通过在较短的字符串中添加新字符串来获得哪些顶点，成本等于添加的字符串的长度。当然，只有当字符串与长边上剩下的t字符重叠时，才能添加字符串。

然后，您的任务是使用Dijkstra算法在该图中找到最短路径，从最初选择的2个不同字符串到t=0的一对。最初对字符串数组进行排序可以使用二进制搜索来查找与所需后缀重叠的字符串(较长的字符串将全部放在一起)，这是一种有效的优化。

Answer 2

这里有一个O(N³)算法，其中N是每个字符串的总长度：

1. 对于S中的每个元素S_i：
   1. 为正则表达式S_i构造一个NFA(S₁|…|S_n)*
   2. 为正则表达式(S₁|…|S_i-1|S_i+1|…|S_n)构造一个NFA*
   3. 构建一个NFA，该NFA是步骤1.1和步骤1.2中的NFA的交集
   4. 在步骤1.3中查找NFA接受的最短字符串
2. 返回步骤1.4中字符串中最短的字符串

---

上述算法可以改进为O(N²logN)：

1. 为正则表达式构造一个NFA(S₁|…|S_n)*
2. 在步骤1中构建两个NFA副本的叉积
3. 对于步骤2中NFA中的每个状态，从该状态中找到NFA接受的最短字符串
4. 让𝒮 ={S}
5. While𝒮不为空：
   1. 从𝒮.
   2. 将T均匀地划分为P和Q
   3. 为正则表达式(P₁|…|P_P)(S₁|…|S_n
   4. 为正则表达式(Q₁|…|Q_Q)(S₁|…|S_n
   5. 在步骤5.3和步骤5.4中构建NFA的叉积，在步骤2中重用NFA
   6. 在步骤5.5中查找NFA接受的最短字符串，重用步骤3的结果
   7. 如果P有一个以上的元素，则将P放入𝒮.
   8. 如果Q有一个以上的元素，则将Q放入𝒮.
6. 返回步骤5.6中字符串中最短的字符串

---

编辑：以下是一个O(N²)算法，从顶部答案改进而来：

1. 设T是S的每个字符串的每个后缀
2. 用T构建一个trie
3. 设G是一个加权有向图。顶点是T的元素，边是：对于S中的每个字符串S_i和T中的T_j，如果S_i=T_j+D或T_1ji+D(使用步骤2中的trie来找到所有这样的对)，将一条从D到T_{3的边添加到S3的加权长度}
4. 求出从空字符串到G中每个顶点的距离
5. 对于S中的每个字符串S_i，S_j(如果S_i)！=S_j和S_i=S_>j+D(使用步骤2中的trie来找到所有这样的对)，找到从空字符串到D的距离(使用步骤4)
6. 答案的长度是步骤5中所有距离中最短距离的的一半。(找到真正的答案很琐碎，但我懒得描述：p)