返回信息流题目链接：
http://121.192.180.203/JudgeOnline/problem.php?id=1090
是由网易笔试题拓展过来做到这题的，网易笔试的字符串规模很小只有50，所以本人暴搜就过了，但是这个长度为10^5，没想到什么好的方法，求助各位大神。[ema20]
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #91229同步于 2016/9/24
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
求问一题平方子串的题目
ayzmkk
2016/9/24镜像同步9 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
你可能估错复杂度了，从最中间往两边数有（1+2+3+…n/2)这已经是O(n*n)了，又有n-1个空，所以复杂度是n的三次方。
我认为这道题要考虑串的性质：
设串1…n符合题意，判断串1……n+2是否满足。
若满足
则先有左右两个串A B Ai=Bi
当多加两项以后 有两个串 C D Ci=Di
对于D的前n/2个项有Di=Bi+1
对于C的前n/2项有Ai=Ci=Bi+1
所以Bi=Bi+1
即B串字符全相等，可知原来的1……n全相等。
那么新加的两个必然是原来的字符。
这说明若从K开始的一段是符合定义的，则在新加了两个以后除非原来的串全等，否则不可能。
同理可证若加4个除非原串间隔一个相等否则不可能。
若4个间隔2。等等。
举例 原来有 1 2 3 4 5 6 7 8
则1=5 2=6 3=7 4=8
现在是12345 678910
则1=6 2=7 3=8 4=9 5=10
因为1=6 2=6 所以1=2 同理2=3
所以在已知长度为N的符合，对之后的N/2个字符可以快速判断。
我觉得会有更好的方法，待我明早想想。
【 在 guyu111 的大作中提到: 】
: 按定义，平方子串长度为偶数，则对子串进行对折其中心处于原串的某个空隙。
:
: 现在考虑这个空隙为(i,i+1)之间，从这个空隙往两边扩展，可以方便的求出以此空隙为中心的平方子串数量，O(n)复杂度
: .........
发自「贵邮」
我逗逼了。试了下超时了
【 在 ayzmkk 的大作中提到: 】
: 三次方肯定超时
:
: 【 在 wk1948 的大作中提到: 】
: : 分治法，可以达到O(n^3)
: :
:
发自「贵邮」