现在的位置: 首页 > 综合 > 正文

poj 3419 求一段区间内的最长不重复子串

2013年06月09日 ⁄ 综合 ⁄ 共 239字 ⁄ 字号 评论关闭

这个题实际上预处理出两个数组就好了,st[i]表示i位置往左最远能延伸到哪里,【st[i],i】为不重复子串

那么在询问一段区间内最长的不重复子串是多长的时候有两种情况 , 对于L R区间内所有的【st[i] , i】,有一部分st[i]是<L的,所以这一部分的值变成了(i - L + 1),

由于st是单调的,显然,,,所以可以二分找出最右的那个i满足st[i]<L,然后左边的部分就是i-L+1,右边的部分就直接用RMQ查询最值就好了,因为这一部分的【st[i],i】完全在L,R区间内。。。。

【上篇】
【下篇】

抱歉!评论已关闭.