CareerCup

// 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;
	}
}

Or do KMP - a little trickier to implement but faster

Yes with the help of Kmp we can do this in O(n) time :)

Or use finite automate.)))

how to implemenet using Finite automata . Can you explain the logic with examples

<pre lang="" line="1" title="CodeMonkey1980" class="run-this"> public static List findSubStringIndex(String str, String substr) {
List<Integer> indexlist = new ArrayList<Integer>();
int j =0;
for(int i=0; i< str.length(); i++) {
if(str.charAt(i) == substr.charAt(j)) {
if(j + 1 == substr.length()) {
indexlist.add(i - j);
j=0;
} else
j++;
}
}

return indexlist;
}</pre><pre title="CodeMonkey1980" input="yes">
</pre>

int *find(string str,string pattern){
int p=0,i;
int arr[20];//initialised to 0
for(i=0;i<str.length()-pattern.length();i++){
int j=0;
int k=i;
while(str[i]==pattern[j]){
k++;
j++;
}
if(j==pattern.length()){
arr[p]=i;
p++;
i=k-1;
}
}
return arr;
}

#include <iostream>
#include <vector>

using namespace std;

int StringIndex(char *s, char *p, int start)
{
        int i, j, k;

        for(i = start; s[i] != '\0'; i++)
        {
                j = i;
                k = 0;
                while(s[j] != '\0' && (s[j] == p[k]))
                {
                        j++;
                        k++;
                }

                if(k > 0 && p[k] == '\0')
                        return i;
        }
        return -1;
}

void patternOcurrences(char *s, char *p)
{
        vector<int> positions;
        int pos, start;
        start = 0;

        for(;;)
        {
                pos = StringIndex(s, p, start);
                if(pos == -1)
                        break;
                positions.push_back(pos);
                start = pos+1;
        }

        vector<int>::iterator it = positions.begin();
        while(it != positions.end())
        {
                cout << *it << "   ";
                ++it;
        }
        cout << endl;
}

int main()
{
        char *str = "xmpabcypstabcpqrabcst";
        char *pattern = "abc";

        patternOcurrences(str, pattern);
        return 0;
}

Use a suffix tree and return the indices!

public int[] PatternMatch(string s, string p){

int sLen = s.length();
int pLen = p.length();
if(sLen == 0 || pLen == 0)
return null;
else if(sLen <pLen)
retrun null;
else{
int k=0 n=0;
int[] match;
while(k<sLen - pLen ){
if(strcmp(s.substr(k, pLen-1), p){
match[n] = k;
n++
}

k++
}
return match;
}

}