CareerCup

Did they want some optimized solution (KMP/Rabin-Karp/FA)? Or you could just use a naive approach?

KMP

kmp

Discussions around string search algos like KMP or Boyer Moore is what should be done.

Why people only know KMP? Boyer Moore is used much more in practice.

#include <iostream>
#include <stdio.h>
#include <cmath>
#include <string>
#include <vector>

using namespace std;


vector<int> prefixtable(string p){
vector<int> temp;
int i=1,j=0;

while(i<p.length()){
if(p[i] == p[j]){
temp.push_back(j+1);
i++;
j++;
}
else if(j>0){
j = temp[j-1];
}
else{
temp.push_back(0);
i++;
}
}

return temp;
}


int kmp(vector<int> temp,string s,string p){
int i=0,j=0;

while(i<s.length()){
if(s[i] == p[j]){
if( j == p.length()-1)
return (i-j);
else{
i++;
j++;
}
}
else if(j > 0){
j = temp[j-1];
}
else{
i++;
}
}
return -1;
}


int main(){
string s,p;
cin>>s>>p;
vector<int> prefix = prefixtable(p);

// for(int i=0;i<prefix.size();i++)
// cout<<prefix[i]<<" ";
// cout<<endl;
cout<<kmp(prefix,s,p)<<endl;
return 0;
}

yay

public class NeedleInHaystack { 
    private static String  substractString (String source,int pos1, int pos2)
    {
        String ret="";
        for (int i=pos1;i<pos2+1;i++)
        {
            ret=ret + source.charAt(i);
        }
        return ret;
        
    }
    private  static int findNeedleInHaystack(String haystack,String needle)
    {
        int ret=-1;
        boolean found=false;
        for (int i=0;i<haystack.length() && !found;i++)
        {
            if (haystack.charAt(i)==needle.charAt(0))
            {
                String hayStackSubstract=substractString(haystack,i,i+needle.length()-1);
                if (hayStackSubstract.equalsIgnoreCase(needle))
                {  
                    ret=i;
                    found=true;
                }
            }
        }
        return ret;
    }
   
    public static void main(String[] args)
    {
        if (args.length==2)
        {
        String hayStack=args[0];
        String needle=args[1];
        System.out.println("hayStack=" + hayStack );
        System.out.println("needle=" + needle );
        int needlePosition=findNeedleInHaystack(hayStack,needle);
        System.out.println(" The needle position is "+needlePosition);
        }
        else{
            System.out.println("Please provie both haystack and needle value");
          }
      }
}

KMP

void Next(char * p, std::vector<int> & next) {
  int n = strlen(p);
  if (p == 0) return;
  next.resize(n, 0);
  int i = 0;
  next[i] = -1;
  int k = next[i];
  while (i < n) {
    while (k >= 0 && p[i] != p[k]) k = next[k];
    i++;
    k++;
    if (i == n) break;
    if (p[i] == p[k]) next[i] = next[k];
    else next[i] = k;
  }
}

char * KMP(char *s, char * p) {
  int s_len = strlen(s);
  int p_len = strlen(p);
  if (p_len == 0) return s;
  std::vector<int> next;
  Next(p, next);
  int i = 0;
  int j = 0;
  while (i < s_len) {
    if (s[i] == p[j]) {
      i++;
      j++;
    }  else j = next[j];
    if (j == p_len) return s + i - p_len;
    if (j == -1) {
      i++;
      j++;
    }
  }
  return NULL;
}

/*
        Implement indexOf function to find a substring from a given string
        So, implement indexOf(String str) from index 0

        Can use KMP as well for O(n) time complexity...
      
        Salesforce interview question
        Facebook question "find needle in haystack"
     */
    public static int indexOf(String str, String substring)
    {
        char[] strArray = str.toCharArray();
        char[] subArray = substring.toCharArray();
        char first  = subArray[0];

        int max = (strArray.length - subArray.length);

        for (int i = 0; i <= max; i++) {
               /* Look for first character of the substring in the original. */
            if (strArray[i] != first) {
                while (++i <= max && strArray[i] != first);
            }
            /* Found first character (i is now at the start of substring in original string), now look at the rest of v2
             * to make sure the whole substring is in the string */

            if (i <= max) {
                int j = i + 1;
                int end = j + subArray.length - 1; //the end index of the substring in the original string
                for (int k = 1; j < end && strArray[j] == subArray[k]; j++, k++);
                if (j == end) {
                    /* Found whole string. */
                    return i;
                }
            }

        }
        return -1;
    }

public static int findNeedleInHaystack(String haystack, String needle){
		int ret = -1;
		int itr = 0;
		int needleLen = needle.length();
		int max = haystack.length() - needle.length();
		
		while (itr <= max){
			String inspectString = haystack.substring(itr, itr + needleLen);
			if (inspectString.equals(needle)){
				ret = itr;
				break;
			}
			itr++;
		}
		return ret;
	}

Fairly certain this is O(n) time. Can definitely be optimized by KMP.

KMP is optimal worst case complexity, hashing is very practical and easy to code, I would start with that.

m = needle.length();
hash function f would be for the form
f(c1c2...cm) = (c1x^(m-1) + c2x^(m-2) + ... + cm) % D where x and D are primes
// precompute x^j for j < m
f(i+1:m+i) = (f(i:m+i-1) - cix^(m-1))*x + c(m+i)
I can pass a moving window on haystack and compute hash(i:i+m-1) efficiently,
use that to filter out mismatches and fallback on character by character comparison when hash values match

Look at entropy of needle and decide on number of hash functions to use, more hash functions if needle has low entropy

int findSubstring(String haystack, String needle)
{
  if(haystack.contains(needle))
    return haystack.indexOf(needle);
  else
    return -1;
}