CareerCup

using suffix array we can find the starting index of sub string.

This could be done by using KMP, but to be honest it won't be easy to write the code during interview if you are not well prepared.

public static int getSubStringStartingPosition(char[] st1, char[] st2)
	{
		int pos=0;
		boolean flag=false;
		
		int k=0;
		for (int i=0; i<=st1.length-1; ++i)
		{
			if ((k <= st2.length-1) && (st1[i]==st2[k]))
			{
				
				if (!flag)
				{
					pos=i;
				}
					
				flag=true;
				k++;
			}
			else
			{
				System.out.println("not found.."+st1[i]);
				if (flag && k <=st2.length-1)
				{
					System.out.println("found an extra character in the middle..");
					pos=0;
				}
			}
		}
		return pos;
	}

int findSubString(const char *input, const char *substring)
{
	int start = 0;
	for (; *input != '\0'; input++ )
	{
		while (*input == *substring)
		{
			substring++;
			input++;
            
			if (*substring == '\0')
				return start;
			if (*input == '\0')
				break;
		}
		start++;
	}
	return -1;
}

bool FindSubString(char* mainstr, char* str)
{
char* start_ptr = mainstr;
char* itr_ptr = mainstr;
char* substr = str;
while(*start_ptr != '\0')
{
substr = str;
while(*substr != '\0' && (*itr_ptr++ == *substr++));

if(*substr == '\0')
return true;

start_ptr++;
itr_ptr = start_ptr;
}
return false;
}

bool FindSubString(char* mainstr, char* str)
{
	char* start_ptr = mainstr;
	char* itr_ptr = mainstr;
	char* substr = str;
	while(*start_ptr != '\0')
	{
		substr = str;
		while(*substr != '\0' && (*itr_ptr++ == *substr++));

		if(*substr == '\0')
			return true;
		
		start_ptr++;
		itr_ptr = start_ptr;
	}
	return false;
}