首页 文章

字符串预处理步骤,在O(1)时间内回答进一步的查询

提问于
浏览
1

给你一个字符串,它包含只包含3个字符的字符 . 说,x y z . 将有百万条查询给你 . 查询格式:x z i j

现在,我们需要找到所有可能的不同子串,这些子串以x开头,以z结尾 . i和j表示子串必须位于的范围的下限和上限 . 它不应该跨越这一点 .

我的逻辑: -

  • 读取字符串 . 有3个数组,分别存储x y z的计数,i = 0直到strlen

  • 将每个字符的索引分别存储在另外3个数组中 . xlocation [],ylocation [],zlocation []

  • 现在,根据查询,(a b i j)找到范围i和j内的b的所有索引 .

  • 为b的每个索引计算答案并将其求和以得到结果 .

是否可以在查询之前预处理此字符串?所以,像这样需要O(1)时间来回答查询 .

1 回答

  • 1

    正如其他人所建议的那样,你可以用分而治之的算法来做到这一点 .

    最佳子结构:如果给出左半部分和右半部分,我们知道左半部分有多少子串,右半部分有多少子串,那么我们可以将两个数字加在一起 . 我们将在左侧开始并在右侧结束的所有字符串中进行计数 . 这只是左子串中的x的数量乘以右子串中的z的数量 .

    因此我们可以使用递归算法 .

    这将是一个问题但是如果我们试图解决所有单个i和j组合,因为底层子问题将被解决很多次 .

    您应该考虑使用动态编程算法来实现这一点,该算法跟踪范围i,j中的子串,在范围i,j和范围i,j中的z .

相关问题