Sometimes it’s good to revise some algorithms and try to implement them in order to get to know, how the built-in functions of high level programming languages actually works. One of the popular problems is string searching. We have many approaches to solve this problem. For example:
- Naive string search algorithm
- Rabin-Karp string search algorithm
- Finite-state automaton based search
- Knuth-Morris-Pratt algorithm
- Boyer-Moore string search algorithm
- Bitap algorithm
This time, I’ve decided to focus on Knuth-Morris-Pratt (KMP) algorithm. It’s quite easy to implement, when you understand it. In addition, its time complexity is quite good and can be defined as O(n).
In this algorithm, we simply go through all letters in a given string and compare them with searched string. When position of searched string reaches length of searched string, we can assume, that our string was found. If two compared letters are different, we set position of searched string to zero and start new search from the next position after which we started searching process before. It’s quite good described on Wikipedia with some pseudo-code. You can also take a look at my code in Java available below, which I’ve written just for practice.
Result of the execution of this program should be as follows:
String found at 15 position.
Please note, that we count position of the letter from zero like in the most cases in Computer Science.
Check this out at: https://github.com/blakeembrey/code-problems.
In this post I will show you my approach to adding reversed numbers.
This problem occurred during the ACM Central European Programming Contest, in Prague in 1998.
General description of the problem
The input consists of N cases (equal to about 10000). The first line of the input contains only positive integer N. Then follow the cases. Each case consists of exactly one line with two positive integers separated by space. These are the reversed numbers you are to add.
For each case, print exactly one line containing only one integer – the reversed sum of two reversed numbers. Omit any leading zeros in the output.
- In the first line of the input, we put number of the lines to process.
- In the next lines, we put numbers split by space, in which we should reverse order of the digits and then add them.
- In the final step, we should reverse order of the digits in the generated data and write result to the output.
Proposal of the solution in the Ruby language
hint: if you cannot see the code below, please disable AdBlock on this site (I don’t have advertisements, but I’m using Gist)