|
Write a function that takes an input string and a pattern string ......
Microsoft Interview Questions and Answers
(Continued from previous question...)
45. Write a function that takes an input string and a pattern string ......
Question:
Write a function that takes an input string and a pattern string and returns a collection of indices of occurences of pattern within the input string.
maybe an answer:
// Rabin-Karp algorithm
/**
* Write a function that takes an input string and a pattern string and returns a collection
* of indices of occurences of pattern within the input string.
*
* N - 'base' string length
* M - 'pattern' string length
*
*/
public final class RabinKarpStringMatcher {
public RabinKarpStringMatcher(String base, String pattern) {
if( base == null || pattern == null ){
throw new IllegalArgumentException("NULL 'base' or 'pattern' string passed: base = '" + base + "', pattern = '" + pattern + "'");
}
this.base = base;
this.pattern = pattern;
this.patternLength = pattern.length();
this.baseLength = base.length();
this.patternHash = calculateHash(pattern, 0, patternLength-1);
}
/**
* Time: O(N+M)
*/
public List<Integer> findMatches(){
if( matchedIndexes == null ){
matchedIndexes = new ArrayList<Integer>();
final int lastIndex = baseLength - patternLength + 1;
BigInteger baseValue = null;
int baseHash = 0;
for( int i = 0; i < lastIndex; i++ ){
if( i == 0 ){
baseValue = calculateValue(base, 0, patternLength-1);
}
else {
baseValue = recalculateValue(base, baseValue, i-1, i+patternLength-1);
}
baseHash = baseValue.mod( BigInteger.valueOf(MODULO) ).intValue();
if( baseHash == patternHash && isBaseEqualToPattern(i) ){
matchedIndexes.add(i);
}
}
}
return matchedIndexes;
}
//==== PRIVATE ====
private final String base;
private final String pattern;
private final int patternLength;
private final int baseLength;
private final int patternHash;
private static final int MODULO = 307;
private static final int BASE = 32;
private static final int BASE_SHIFT = 5; // pow(2, BASE_SHIFT) = BASE
private List<Integer> matchedIndexes;
/**
* Time: O(M)
*/
private boolean isBaseEqualToPattern(int from){
for(int j = 0; j < patternLength; j++ ){
if( base.charAt(from+j) != pattern.charAt(j) ){
return false;
}
}
return true;
}
/**
* Time: O(M)
*/
private BigInteger calculateValue(String str, int from ,int to){
BigInteger value = BigInteger.valueOf(0);
for( int i = from; i < to+1; i++ ){
value = value.multiply( BigInteger.valueOf(BASE) ).add( BigInteger.valueOf(str.charAt(i)) );
}
return value;
}
/**
* Time: O(M)
*/
private int calculateHash(String str, int from ,int to){
int hash = 0;
for( int i = from; i < to+1; i++ ){
hash = ( hash * BASE + str.charAt(i) ) % MODULO;
}
return hash;
}
/**
* Time: O(1)
*/
private BigInteger recalculateValue(String str, BigInteger hash, int from ,int to){
final int h = 1 << ( BASE_SHIFT * (to-from-1));
BigInteger newHash = hash.subtract( BigInteger.valueOf(str.charAt(from)).multiply( BigInteger.valueOf(h) ) );
newHash = newHash.multiply( BigInteger.valueOf(BASE) );
newHash = newHash.add( BigInteger.valueOf(str.charAt(to)) );
return newHash;
}
}
(Continued on next question...)
Other Interview Questions
| 