CareerCup

Approach :
1. Set the iterator to the first position in the input string.
2. Look for first character match.
3. Store the iterator into lookup Iterator.
4. If it matches till the lookup string return true
5. Else Increment the iterator and move to step 2.

bool IsSubstring(char * inputString, char * lookupString){
    int lenOfLookupString = strlen(lookupString);
     for(int i=0;*(inputString+i);i++){
        if(inputString[i] == lookupString[0]){
            int k=0;
            while(inputString[i+k] && k< lenOfLookupString){
               if(inputString[i+k] != lookupstring[k])
                   break;
             }
             if(k == lenOfLookupString){
                return true;
             }
        }
        i++;
    }
    return false;
}

strstr(src,substring);
//detects first occurrence of substring and returns pointer at that location, otherwise returns NULL

Sir...i think they would prefer a O(n) solution..KMP is the way to go..even a child can write strstr

suffix tree...

This seems a more clean and concise code in O(n) complexity with test cases as well.

bool containsString(char str1[], char str2[]){
	int lenOfFirstString = sizeof(str1)/sizeof(char) - 1;
	int lenOfSecondString = sizeof(str2)/sizeof(char) - 1;

	// Check for error conditions
	if(lenOfFirstString == 0 || lenOfSecondString == 0 || lenOfSecondString > lenOfFirstString) return false;
	
	int posInStr1 = posInStr2 = 0;

	while( posInStr1 < lenOfFirstString){
		
		if(str1[posInStr1++] == str2[posInStr2]){ // Increment str2 pointer when an equal char is found 
			posInStr2++;
			if(posInStr2 == lenOfSecondString) //When entire second string has been found
				return true; 
		}

		else posInStr2 = 0;

	}
	
	return false;
}

Hey, the above code would fail for eg: str1=abbcd and str2=bc.
So this code should work fine now with complexity O(n).

bool containsString(char str1[], char str2[]){
	int lenOfFirstString = sizeof(str1)/sizeof(char) - 1;
	int lenOfSecondString = sizeof(str2)/sizeof(char) - 1;
	// Check for error conditions
	if(lenOfFirstString == 0 || lenOfSecondString == 0 || lenOfSecondString > lenOfFirstString) return false;	
	int posInStr1 = posInStr2 = 0;
	while( posInStr1 < lenOfFirstString){
		if(str1[posInStr1++] == str2[posInStr2]){ // Increment str2 pointer when an equal char is found 
			posInStr2++;
			if(posInStr2 == lenOfSecondString) //When entire second string has been found
				return true; 
		}
		else if(posInStr2 > 0){
				posInStr1--; // So that we can start comparing from the previous mismatched position
				posInStr2 = 0;
		}
	}
	return false;
}

Hmm, can anybody find test cases to break this ?

@sdcareer7
Check with the input str1="aaabc" and str2="aab"

#include <cstring>
#include <cmath>

int greedyMatch(char* find, char* replace, char* str)
{
	int strLength = strlen(str);
	int findLength = strlen(find);
	int matchCount = 0;

	int x, z; x = z = 0;
	for (int i = 0; i < strLength; ++i)
	{
		if (find[x] == str[i])
		{
			if (x == findLength - 1)
			{
				++matchCount;
				x = 0;
				continue;
			}
			++x;
		}
		else
		{
			if (i == strLength - 1)
				break;
			x = 0;
			++z;
			i = abs(matchCount - z) - 1;

		}
	}
	return matchCount;
}

use the knuth patterson algorithms for this problem.

//Well mine looks very simple as compared to rest of sols posted , am i missing
something

int substring(string &source, string& substr){
	
	char *p1 = &substr[0];
	char *s1 = &source[0];
	char *temp = p1;
	while(*s1 != '\0'){
	
		if( *p1	== *s1 ){
			p1++;
			if(*p1 == '\0')
				return 1;
		}else{
			p1 = temp;
		}
	   s1++;
	}

	 return -1;
}

Guys, string searching is a typical problem and has been studies for years.
Half dozen algorithms are out there:
en.wikipedia.org/wiki/String_searching_algorithm

No need to scratch your head, just study those.

below is the simplest implementation but takes O(m*n) time, any ideas how to make it O(n)..couldnt understand the KMP algo

public class SubString {

    public static void main(String[] args){


        String str=new String();
        String substr=new String();

        Scanner s=new Scanner(System.in);
        System.out.println("Enter the String");
        str=s.nextLine();

        System.out.println("Enter the Sub String");
        substr=s.nextLine();

        int j=0;
        int i;

        for(i=0;i<str.length();){

            if(str.charAt(i)==substr.charAt(j)){

                if(j==substr.length()-1) {

                 break;

                 }

                j++;
                i++;

            }

            else {
                i=i-j+1;
                j=0;

            }
            }


        if(j==substr.length()-1) {

            System.out.print("Substring found in main String at position  " +(i-j));
        }


        }

    }

class postiion_of_string_in_another_String
{
public static void main(String []args)
{
String input = new String("carrerstack");
Pattern pattern = Pattern.compile("stack");
Matcher match = pattern.matcher(input);
String string = "";
if(match.find())
{
string = match.group();
}
System.out.println(input.indexOf(string));
}
}

public class position_of_a_string_in_another_string
{
public static void main(String []args)
{
position_of_a_string_in_another_string obj = new position_of_a_string_in_another_string ();
System.out.println(obj.findPositionOfString("careerstack","stack"));

}

private int findPositionOfString(String word1, String word2)
{
StringBuilder out = new StringBuilder();
int array [] [] = new int [word1.length()+1][word2.length()+1];

for(int i =0;i<word1.length();i++)
{
for(int j =0;j<word2.length();j++)
{
if(word1.charAt(i) == word2.charAt(j))
{
array[i+1][j+1] = array[i][j] + 1;
}
else
{
array[i+1][j+1] = Math.max(array[i][j+1], array[i+1][j]);
}
}
}

for(int x = word1.length() , y = word2.length() ; x!=0 && y!=0;)
{
if(array[x][y] == array[x-1][y])
{
x--;
}
else if(array[x][y] == array[x][y-1])
{
y--;
}
else
{
out.append(word1.charAt(x-1));
x--;
y--;
}
}


int index = word1.indexOf(out.reverse().toString());
return index;

}
}