Блог пользователя ar_rony1

Автор ar_rony1, история, 3 года назад, По-английски

How can i solve following problem using string hashing? SUB_PROB

  • Проголосовать: нравится
  • -1
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Use Rabin-Karp Algorithm. It uses string hashing.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Isn't the time limit too strict for Rabin-Karp?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Rabin-karp complexity is O(n*m) and this problem time limit is 0.100s. So what will be the better approach?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I couldn't come up with anything using string hashing, but the problem might be solved using suffix array with complexity O(MlogM + N*logM). (still not sure if it's gonna pass since time limit is too tight) You can check it out here.