# Software Programming

Kunuk Nykjaer

## Interview-question: How to find all permutations of a given word in a given text? – Java example

with one comment

Write a function (in Java) to find all permutations of a given word that appear in a given text. For example, for word abc and text abcxyaxbcayxycab the function should return abc, bca, cab.

To find a permutation of a string you can use number theory.

There is a method where you can calculate a hash of a string using prime numbers. Every permutation of the same string will give the same hash value. All other string combination which is not a permutation will give some other hash value.

The hash-value is calculated by c1 * p1 + c2 * p2 + … + cn * pn
where ci is a unique value for the current char in the string and where pi is a unique prime number value for the ci char.

Here is the implementation.
Main.java

```// Author: Kunuk Nykjaer
public class Main {
final static int[] primes = new int[] { 2, 3, 5, 7, 11, 13, 17,
19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113 };

public static void main(String[] args) {
final char[] text = "abcxaaabbbccyaxbcayaaaxycab"
.toCharArray();
int hash = val(new char[]{'a','b','c'});
for (int i = 0; i < text.length - 2; i++) {
char[] _123 = new char[]{text[i],text[i+1],text[i+2]};
if(val(_123)==hash){
System.out.println(new String(_123) );
}
}
}
static int p(char c) {
return primes[(int)c - (int)'a'];
}
static int val(char[] cs) {
return
p(cs[0])*(int)cs[0] + p(cs[1])*(int)cs[1] + p(cs[2])*(int)cs[2];
}
}
```

The output is: abc bca cab

Written by kunuk Nykjaer

May 25, 2012 at 1:20 pm

Posted in Algorithm, Java

Tagged with