Algorithms

Searching word in a string with KMP algorithm

2015-07-22 Algorithms, Java No comments

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.

Code Problems

2013-06-15 Algorithms, JavaScript No comments

I’ve recently found really cool repository containing a lot of different code problems and solutions for them. Most of the code is written in JavaScript. Quote from GitHub page:

This repo is full of code problems that I have received prior or during an interview. I’ll present all my solutions here in JavaScript, but feel free to add your own solutions in another language and even optimise my solutions. If you have your own code problems you would like to contribute, I would love to see them as well.

Check this out at: https://github.com/blakeembrey/code-problems.

Adding reversed numbers

2013-01-21 Algorithms, Ruby No comments

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

Input

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.

Output

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.

Example

Sample input:

3
24 1
4358 754
305 794

Sample output:

34
1998
1

Solution

Exemplary approach

  1. In the first line of the input, we put number of the lines to process.
  2. In the next lines, we put numbers split by space, in which we should reverse order of the digits and then add them.
  3. 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)