首先我们考虑第一种做法，我们搜索 \(dp_{x,y,l,r}\) 判断 \(s[x,y]\) 和 \(t[l,r]\) 是否等价，同时记忆化搜索。
但是这样是很明显不行的。如果长度是 \(2\) 的整次幂，我们仅分析最底层长度为 \(1\) 的区间，我们发现，任何的 \([x,x][y,y](x\le n/2)\)，都会被搜到一遍。这个可以递归处理，假设它们的父亲区间是 \([a,b][c,d]\)，那么只要 \([a,b][c,d]\) 被调用，\([x,x][y,y]\) 就会作为 \([a,b][c,d]\) 分别的子区间被调用。而这样一直回溯到公共祖先 \([1,n][1,n]\)，这个是显然会被调用的。所以任意的 \([x,x][y,y]\) 都被调用。故仅这一层就会有 \(n^2\) 个函数被调用。
我们考虑加上一个小优化，我们每次先用哈希判断一下 \(s[x,y]\) 和 \(t[l,r]\) 是否相同，如果不同再往下查询。实际上，这个做法的效率是很高的。因为在字符集有限的情况下，同样的字符集能构成的字符串一共只有 \(2^k\) 个。所以，在效率最低的深层，因为字符串短，所以撞起来的概率还是非常大。
https://codeforces.com/contest/559/submission/212986413
或者，我们还可以采用另一个优化。就是，如果 \(s[x,y]\) 分出的两个子串相等，那么就只用 \(s\) 的左部分递归即可。这样使得下方剩下的记忆化搜索的优化率提高。但是，虽然这种情况出现的概率和前一个差不多，可是它的优化有限，不能直接终止一条递归路径。优化幅度不如前一个大。
https://codeforces.com/contest/559/submission/212987266
两个都采用的程序：
https://codeforces.com/contest/559/submission/212809958
这些优化都是对“答案相同”优化的。而在答案不同的情况下，我们就需要对不同的单元递归到底。我们可以找到问题就退出，但是如果问题在最后就会稍慢。我们考虑每次随机顺序进行递归，随机的挑选前一个和后一个，所以在每个点选择不优路径的概率只有 \(0.5\)，并且因为完全相同了，可以很快调整过来。
再加上随机优化：
https://codeforces.com/contest/559/submission/95525190
然后，考虑别的思路。既然底层撞字符串的概率很大，以至于我们可以直接哈希判断，那么为什么对字符串进行记忆化搜索呢？我们不记忆区间而记忆字符串本身，就能享受到字符串本质不同数量少的福利，也就相当于进行了前一个优化。
但是这样做就卡一些，因为带 \(\log\) 而且 map 里面放的是 string，执行一次 cmp 操作都要好半天。所幸长字符串不会太多且方便比较，还是可以卡过去的。
https://codeforces.com/contest/559/submission/159248124
但是，这道题是有确定复杂度的正解的。我们考虑最小表示，将 \(s\) 和 \(t\) 分别表示成和它们等价的字典序最小的字符串，然后直接比较。
最小表示可以递归完成，我们只需要实现求 \([l,r]\) 的最小表示，就是把左半边和右半边分别最小表示之后，把更小的一个放在前面。递归的调用就可以得到答案。递归共 \(\log n\) 层，每层加起来都是扫整个字符串，所以复杂度是 \(O(n\log n)\) 的。
https://codeforces.com/contest/559/submission/212791399
不过，这道题不知道是前面的做法优化量太大还是数据过水，最后的确定复杂度做法和前面的一众玄学优化有着差不多的表现。
标签：submission,递归,com,Equivalent,codeforces,CF559B,字符串,优化,Strings From： https://www.cnblogs.com/jucason-xu/p/17539668.html