CareerCup

Yeah, I agree that you should rabin-karp, but instead of one hash, you should have also the second one, counted for a word that was reversed, and match against those two hashes instead of one.

In an interview setting , use rabin karp.

i = 0;
j = 0;
i_rev = 0;
j_rev = 0;
number_of_occurence = 0
while(i<haystack.length && j <needle.length)
{
if (haystack[i] == needle[j])
{
i++;
j++;
if (j == needle.length())
number_of_occurence++;
}
else
{
i = i - j + 1
j = 0
}
if(haystack[i_rev] == needle[j_rev])
{
i_rev++;
j_rev++;
if (j_rev == needle.length())
number_of_occurence++;
}
else
{
i_rev = i_rev - j_rev + 1
j_rev = 0
}
}

return number_of_occurence;

if (ispalindrome(teststring))
     return numsubstring(string, teststring);
else
    return numsubstring(string, teststring) + numsubstring(string, rev(teststring) ) ;

exercise:
design ispalindrome(), numsubstring( , ), rev()

Use two Suffix Trees, one for the normal word and one for the reverse string. Then return the occurrences of the substrings by calling SuffixTree#search(substring).

String search in O(m) complexity, where m is the length of the sub-string (but with initial O(n) time required to build the suffix tree for the string)

Link: en.wikipedia.org/wiki/Suffix_tree

public static string reverse(String s) 
        {
            int start = 0;
            int end = s.Length - 1;
            char temp;
            StringBuilder str = new StringBuilder(s);
            
            while (start < end) {
                temp = str[start];
                str[start] = str[end];
                str[end] = temp;
                start++;
                end--;
            }

            return str.ToString();
        }

        public static int compare(string sfirst, string ssecond)
        {
            StringBuilder s1 = new StringBuilder(sfirst);
            StringBuilder s2 = new StringBuilder(ssecond);

            int count = 0;
            bool equals;
            for (int i = 0; i <= s2.Length - s1.Length; i++)
            {
                equals = true;
                for (int j = 0; j < s1.Length; j++)
                {
                    if (s1[j] != s2[i + j])
                        equals = false;
                }
                if (equals)
                    count++;
            }
            return count;
        }

public class RabinKarp {
	
	private String pat; // the pattern string.
	private long patHash; // the hash of the pattern
	private long Q; // a large prime number, small enough to avoid overflow.
	private int M; // pattern string length.
	private long RM; // R ^ (M - 1) % Q
	private int R; // radix.
	
	public RabinKarp(String pattern){
		pat = pattern;
		M = pat.length();
		R = 256;
		Q = longPrimeNumber();
		patHash = hash(pat);
		RM = 1;
		for(int i = 1; i <= M - 1; i ++){
			RM = (RM * R) % Q;
		}
	}
	
	public void search(String txt){
		int N = txt.length();
		if(N < M){
			System.out.println(N);
		}
		
		// Compare pattern and first M - character sequence in text string.
		long txtHash = hash(txt);
		if(patHash == txtHash && check(txt, 0)){
			System.out.println(0);
		}
		
		for(int i = M; i < N; i ++){
			txtHash = (txtHash - RM * txt.charAt(i - M)) % Q;
			txtHash = (R * txtHash + txt.charAt(i)) % Q;
			if(txtHash == patHash && check(txt, i - M + 1)){
				System.out.println(i - M + 1);
			}
		}
	}
	
	// Check if pattern equals the corresponding M - character sequence in text string.
	public boolean check(String txt, int offset){
		for(int i = 0; i < M; i ++){
			if(pat.charAt(i) != txt.charAt(i + offset)){
				return false;
			}
		}
		return true;
	}
	
	// Get a hash value of a string of length M
	public long hash(String key){
		long h = 0;
		for(int i = 0; i < M; i ++){
			h = (R * h + key.charAt(i)) % Q;
		}
		return h;
	}
	
	// Get a 31-bit prime number
	public long longPrimeNumber(){
		BigInteger probablePrime = BigInteger.probablePrime(31, new Random());
		return probablePrime.longValue();
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		String pat = "abc";
		String txt = "abcddbsabcba";
		RabinKarp rk = new RabinKarp(pat);
		rk.search(txt);
		System.out.println("----------");
		StringBuilder sb = new StringBuilder(pat);
		RabinKarp rk1 = new RabinKarp(sb.reverse().toString());
		rk1.search(txt);
	}

}

simple version of Rabin Karp

public class Occurences {

    public static void main(String[] args) {
        String string = new String();

        string = "hello worlord";

        String pattern = new String();

        pattern = "or";

        int hashValue = 0;

        Occurences occ = new Occurences();

        boolean ok = false;


        int patHash = occ.calculateHash(pattern, 0, pattern.length(), 0);
        int wordHash = 0;

        for (int i = 0; i < string.length() - pattern.length(); i++) {

            wordHash = occ.calculateHash(string, i, i + pattern.length(), wordHash);

            if (patHash == wordHash)
                ok = true;


            for (int k = 0; k < pattern.length() && ok == true; k++) {
                if (pattern.charAt(k) == string.charAt(i + k))
                    ok = true;
                else
                    ok = false;

            }
            if (ok == true) {
                System.out.println("Pattern found at position:  " + i);
            }
        }

    }

    int calculateHash(String str, int i, int length, int hashValue) {
        if (i == 0) {
            for (int k = 0; k < length; k++)
                hashValue += str.charAt(k);
        } else {
            hashValue += str.charAt(length - 1);
            hashValue -= str.charAt(i - 1);

        }
        return hashValue;

    }

}

void CountWords(string txt, string str, int &cnt)
{
	if(txt.size()==0 || str.size()==0)
		return;
	int start=0;
	int index=0;
	int n=txt.size();

	while(start!=n)
	{
		index=txt.substr(start,n).find(str);
		if(index!=string::npos)
		{
			cnt++;
			start+=(index+str.size()-1);
		}
		else
			start++;
	}
}
int main()
{
	string txt="   PUT SOURCE STRING HERE  "; 
	string str=" PUT STRING TO BE SEARCHED HERE ";
	int cnt=0;

	CountWords(txt,str,cnt);
	reverse(str.begin(),str.end());
	CountWords(txt,str,cnt);

	cout<<"Total Count:\t"<<cnt<<endl;
	return 1;
}