aka.Sohieb's blog

String Matching Problem
By aka.Sohieb, history, 9 years ago, In English

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

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
9 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

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..

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

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

      → Reply