I would like to ask a simple question about the algorithm. This is about the KMP
ID: 3842611 • Letter: I
Question
I would like to ask a simple question about the algorithm. This is about the KMP or the Knuth-Morris-Pratt algorithm. How can we apply it to our daily activities or how is it reflected in our daily living? and can you explain to me it's relevance to the activity? I hope you can give many examples if possible. Thank you so much
I hope you can give me different instances in our daily life (example riding the subway, map reading etc) and hope you can also explain the relevance of the algorithm. thank you so much
Explanation / Answer
In real world KMP algorithm is used in those applications where pattern matching is done in long strings, whose symbols are taken from an alphabet with little cardinality. A relevant example is the DNA alphabet, which consists on only 4 symbols (A,C,G,T). Imagine how KMP can work in a "DNA pattern matching problem": it is really suitable because many repetition of the same letter allows many jumps, and so less computation time wasted. If you are interested in this resarching area just google "DNA pattern matching algorithms", there's a lot to say.
similarly it is also used in map reading