Open nagato1208 opened 5 years ago
https://nagato1208.github.io/2019/08/23/leetcode-1163-Last%20Substring-in-Lexicographical-Order/#more
描述给一个字符串,返回字典序最大的substring. 思路常规解法是后缀数组(倍增法), 然后拿到sa数组最后一个元素(最大substring起始点). 最优解是用类似字符串最小表示法的O(n)解, 维护两个指针i,j表示当前正在比较的两个substring的起始点, 另一个k表示substring长度. 每次比较发生在s[i+k]和s[j+k]之间. match就k+1否则更新i,j. 当k
https://nagato1208.github.io/2019/08/23/leetcode-1163-Last%20Substring-in-Lexicographical-Order/#more
描述给一个字符串,返回字典序最大的substring. 思路常规解法是后缀数组(倍增法), 然后拿到sa数组最后一个元素(最大substring起始点). 最优解是用类似字符串最小表示法的O(n)解, 维护两个指针i,j表示当前正在比较的两个substring的起始点, 另一个k表示substring长度. 每次比较发生在s[i+k]和s[j+k]之间. match就k+1否则更新i,j. 当k