bayram's blog

Can anyone explain Knuth–Morris–Pratt algorithm ?
By bayram, 11 years ago, In English

I read this algorithm 5 times on wikipedia.org and didn't understood.
(sorry for my poor english)

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

Comments Comments (16)
| Write comment?
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

didn't understood = false didn't understand = true

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

    thanks!

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

    Does "didn't understood" have a meaning, so you can deduce its logical value :P?

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

http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm see this one :)

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

if you can read russian, see it: e-maxx.ru/algo/prefix_function

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

    Chrome can translate a whole page .....

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

      Thanks!

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

      can u guyz just explain me why my upper comment is downvoted 8 time (yet...I think more to come) !!!!!!!!??????? it would be very nice of u !!! perhaps i could learn how to behave well in social network !!!! (expecting more downvote for this....!!!!)....embarrassing !!!!!!!

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

        I think it's because automatic translators just aren't good enough to translate technical texts (or almost any text, for that matter).

        → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

thanks to everybody. I understood it now.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Topcoder has a nice Tutorial.

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

    It will surely be of great help for someone who posted it 2 years ago :P

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

      But maybe there will be one less topic asking to explain KMP because this link will be helpful to someone? :D

      → Reply
»
3 years ago, # |
  Vote: I like it -51 Vote: I do not like it

This tutorial is great. http://www.btechsmartclass.com/data_structures/knuth-morris-pratt-algorithm.html and for code, you can find it anywhere.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, Did you notice that he posted this blog 8 years ago?

    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Time complexity of prefix function is still mystery to me :(

→ Reply