问题如下：给定一个有向无环图，其中每个节点都标有一个字符，找到图中形成回文的所有最长节点路径。
我想到的最初解决方案是简单地枚举图形中的所有路径。这有效地生成了一堆字符串，然后我们可以在这些字符串上应用 Manacher 算法来查找所有最长的回文。但是，这似乎并不那么有效，因为图中的路径数量在节点数量上呈指数级增长。
然后我开始考虑直接在图上使用动态规划，但我的问题是我无法弄清楚如何构建我的"动态规划数组"。我最初的尝试是使用二维布尔数组，其中 array[i][j] == true 表示节点 i 到节点 j 是一个回文，但问题是从 i 到 j 可能有多个路径。
我已经在这个问题上停留了一段时间，现在我似乎无法弄清楚，任何帮助将不胜感激。
Manacher算法的线性时间技巧依赖于这样一个事实，即如果您知道以字符 15 为中心的最长回文的长度为 5(字符 13-17(，并且有一个以节点 19 为中心的长度为 13 的回文(字符 13-25(，那么您可以跳过计算以字符 23 为中心的最长回文 (23 = 19 + (19 - 15((，因为你知道它只是以字符 15 为中心的镜像。
使用DAG，您没有这种保证，因为回文可以向任何方向移动，而不仅仅是向前和向后。但是，如果你有一个从节点m到节点n的候选回文路径，你是否可以将该字符串扩展到更长的回文并不取决于m和n之间的路径，而只取决于m和n(以及图本身(。
因此，我会这样做：
首先，按拓扑顺序对图节点进行排序，以便您有一个节点索引的数组s[]，并且从s[i]到s[j]的边意味着i < j。
我还假设您构建了一个逆数组或哈希结构sinv[]以便0..nodeCount-1中j的所有整数和所有节点索引ns[sinv[j]] == j和sinv[s[n]] == n。
此外，我假设您有函数graphPredecessors、graphSuccessors和graphLetter，它们获取节点索引并分别返回图形上的前置任务列表、后继事件列表或该节点上的字母。
然后，制作一个大小为nodeCount的整数的二维数组，称为rnodeCount。当r[i][j] = y和y> 0 时，将意味着如果存在从s[i]的后继者到s[j]的前身的回文路径，那么可以通过在前面添加s[i]和在后面添加s[j]来扩展该路径，并且可以通过在每个方向上y多个节点(包括s[i]和s[j](来继续扩展：
for (i=0; i < nodeCount; i++) {
for (j=i; j < nodeCount; j++) {
if (graphLetter(s[i]) == graphLetter(s[j])) {
r[i][j] = 1;
for (pred in graphPredecessors(s[i])) {
for (succ in graphSuccessors(s[j])) {
/* note that by our sorting, sinv[pred] < i <= j < sinv[succ] */
if (r[sinv[pred]][sinv[succ]] >= r[i][j]) {
r[i][j] = 1 + r[sinv[pred]][sinv[succ]];
}
}
}
} else {
r[i][j] = 0;
}
}
}
然后找到0..nodeSize-1中x的r[x][x]最大值，以及从s[lft]到s[rgt]有边的r[lft][rgt]的最大值。将该最大值称为M，并说您在位置[i][j]中找到了它。每对这样的i，j对将代表最长回文路径的中心。只要M大于1个，就可以通过在graphPredecessors(s[i])中查找一个pred，在graphSuccessors(s[j])中找到一个succ来扩展每个中心，以便r[sinv[pred]][sinv[succ]] == M - 1(回文现在pred->s[i]->s[j]->succ(。然后，您可以通过查找r值为M - 2等的适当索引来扩展它，当您到达r中的值1的位置时停止。
我认为这个算法总体上以O(V^2 + E^2)的运行时结束，但我并不完全确定这一点。