CareerCup

Build a hash look up table of all chars in src string. Then scan find string and return index of first char that exists in look up table.

Please read the the problem well :) Kmp is too bid cannon for this!

The fastest is: as there are less than 32 character types (let's suppose it is not Unicode) you can represent the search values in an integer: go through the find array and OR it's shifted values to the integer, marking the bit 1 if it's a searchable char (a> 0001 b>0010 ...)

Then start processing the the input, AND ing all shifted values to this array. If the result is greater than 0 that is your first match.

Please note that even though hashtable is considered to be O(1) no interviewer will accept the answer for a fixed size input as optimal ;)

Maybe, we can also sort the src string, and for each character in finding string, we perform a binary search in src string to see if src string also has such character. It will be slower, however, save spaces

- Add every char from src to unordered_hashmap with the char as key and no of times it occurs in the src string as value
- hence, src will be transformed as (g,2) (a,2) and (b,2) in the map.
- now check if every char from "find" string is is present in the map.
- if any char is found, find the index of that char in the "find" string and thats it !
- fetching from map is O(1)
- looking up every char from "find" takes O(n) where n=strlen(find)
- additional space of O(n) for the map !

Use KMP to do it in o(n).

CAA: Create Auxilary Array
MFC: Match First Character
a: find string
b: src sring
c: aux string
t: temp int va;ue
CAA()
	c[n] ={0}
	for each i from 0 to n-1
		t = a[i] - 'a'
		c[t] ++

MFC()
	for each i from 0 to m-1
		t = b[i] - 'a'
		if(c[t] != 0)
			print b[i]
			return

main
	CAA()
	MFC()