Readme

2573.Find-the-String-with-LCP

首先，我们知道，如果lcp[i][j]>=0，那么一定意味着s[i]==s[j]，这意味着我们知道任意两个字符是否相等的信息。假设LCP的信息是准确的，那么仅凭这些信息我们就可以充分地构造出字符串来。

我们先考察s中第一个未填写的位置i，此时必然是s[0]。由于我们只有字符相等的约束，而没有字符大小的约束，所以为了构造字典序最小的字符串，我们必然将s[0]填写为'a'。此时我们只需要考察所有lcp[0][j]>0的位置j，那么必然有s[j]=s[0]='a'。当然如果我们发现s[j]已经被填写过了且不是'a'，那么说明引出了矛盾，可以直接返回无解。

接下来我们考察s中第二个未填写的字符i。注意这个位置可能不一定是s[1]，因为s[1]可能已经由于一些相等关系的约束而已经填写了。同样，为了使得字典序最小，我们必然将s[i]置为'b'。此时我们只需要考察所有lcp[i][j]>0的位置j，那么必然有s[j]=s[i]='b'。当然如果我们发现s[j]已经被填写过了且不是'b'，那么说明引出了矛盾，可以直接返回无解。

依次类推，我们可以将26个字母顺次填入s未填充的位置上。如果最后还有一些位置没有填充完，说明无法用26个英文字符完成任务。

以上得到的s是基于LCP可信赖的前提。但是LCP本身可能是有问题的，比如lcp[0][2]=3但是lcp[1][3]=4，这样的信息是矛盾的。所以我们还需要检验基于s的LCP矩阵的准确性。求任意两个位置的LCP，这本质就是求一个双序列的DP，用两层循环即可实现。