首页 > 代码库 > Codeforces gym Hello 2015 Div1 E
Codeforces gym Hello 2015 Div1 E
Codeforces gym Hello 2015 Div1 E
Codeforces gym 100570 problem E
（一种处理动态最长回文子串问题的方法）
Problem
给一个长度为N的字符串S，字符集是‘a’－‘z‘。进行Q次操作，操作分三种。一，修改位置X的字符为C；二，查询以P位置为中心的最长回文子串的长度，并输出；三，查询以P与P+1的中间位置为中心的最长回文子串的长度，并输出。
More
第二种操作子串长度为奇数，一定存在；第三种操作子串长度为偶数，若不存在，输出 -1。
Limits
Time Limit(ms): 4000（1s足以）
Memory Limit(MB): 256
N, Q: [1, 10^5]
S[i], C: [‘a‘, ‘z‘]
X, P: [1, N]
Solution
（Thanks Fcdkbear）
More
对于第二、三种操作，用hash和二分搜索来查询长度。由于中心位置P给定，所以每次查询复杂度为O(log)*O(hash)。
用线段树来hash，hash方程为：H(Si+1Si+2...Si+n-1Si+n)=H(Si+1Si+2...S(2i+1+n)/2)*(prime^k)+H(S(2i+1+n)/2+1...Si+n-1Si+n)；其中prime为选定的素数，选择10^9+7可以过，k为S(2i+1+n)/2+1...Si+n-1Si+n的长度，即k=(i+n) - ((2i+1+n)/2+1) +1；用上述方程，线段树父亲结点hash值由孩子hash值来维护，即可在O(hash)=O(logN)的复杂度内查询任意一子串的hash值。
这种字符串hash的方法理论上有风险，但有很大的概率不发成冲突。
Complexity
Time Complexity: O(Q*logN*logN)
Memory Complexity: O(4*N)
Source
Codeforces gym Hello 2015 Div1 E
Code
Codeforces gym Hello 2015 Div1 E From My Github
Codeforces gym Hello 2015 Div1 E
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。