Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

Блог пользователя aka.Sohieb

String Matching Problem
Автор aka.Sohieb, история, 8 лет назад, По-английски

I was trying to solve this problem ( Ransom Note ) but failed, i can not find any algorithm to solve this with the given constrains, and i searched for any solution to this problem but not found any.

Could anyone tell me a hint or an appropriate algorithm to solve this!!

thanks in advance :)

UPD

I solved it using a hint from jcg, and this is my code

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

»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +7 Проголосовать: не нравится

Well, greedy works here. You can try to match the longest prefix of the note in the newspaper (case insensitive), add this prefix to the answer; and continue with the remaining part of the note... To match efficiently you can build a suffix tree or a suffix automaton of the newspaper.. I will try to implement it and put the code here..

UPD: Actually this solution has a problem... When we match insentive and there are two options (the lower and upper case letter) we have to consider both because we don't know who will give us the longest prefix in the future, and this generate an exponential cases in the math.. Anybody has a solution for this issue..

→ Ответить
  • »
    »
    8 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

    I implemented this idea using suffix array but dont understand the problem you found in this idea,

    i build the suffix array with only lowercase letters and match with it, and when printing the answer i print it as the original case.

    i got WA but i think i have some bug.

    this is my code, what do you think?! is it a logic problem or bug in this implementation?!!

    UPD I found the bug i got AC, here is my code, and thanks for your idea :)

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      You are right, what I said is not an issue.. I'm glad that you solve it..

      → Ответить