先说一下自己的SAM做法：
看到回文串我们首先考虑对以下字符串建立SAM：正串+特殊字符1+特殊字符2+反串。这样也许能有一点用。晚上睡觉前我考虑的是对于正串的endpos在反串中也是一样的endpos，这样只需要找到他们在parent tree的LCA就可以确定LCA的祖先是一个回文串了，因此可以O(nlogn)的计算答案。
但是早上突然想到假了，因为正串的endpos在反串中体现为所谓的beginpos，而我们有的只是endpos，反串对应的endpos其实是正串的beginpos，而两者我们没办法搞定，这个做法告一段落（？）
但事实上我们也不是不能优化，我们发现对于回文中心，他会在正串中做endpos，也会在反串中做endpos并且两串加起来还一定是一个回文的字符串，
标签：Palindromes,APIO2014,endpos,反串,正串,回文 From： https://www.cnblogs.com/IceYukino/p/17184393.html