CareerCup

The simplest way is to for every character check the following n characters (where n is the length of the substring) to see whether they equal. This approach is O(N_String * N_Substring).

A better approach is to use the Knuth-Morris-Pratt algorithm en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm which achieves O(N_String) performance but it's probably too involved for an interview question. But knowing it exists would probably be worth some brownie points.

There are lots of string search algorithms.

1. Brute force ( Moving by 1 till end )
2. Rabin Karp ( Use rollover hashing )
3. Horspool ( Shifting to last matched item )
4. KMP ( Create DFA and use it for searching )

You can use any of the above four. I feel KMP is faster then others when string contains repeated characters.

There is the famous KMP Algorithm for this

int substring(char *str,char *substr)
{
int i,j=0,len,len2;
len=strlen(substr);
len2=strlen(str);
for(i=0;i<len2-len;i++)
{
if(*(str+i)==*(substr+j))
{
j++;
}
if(j==len)
return(0);
}
if(j==len)
return(0);
else
return(1);
}

I wrote in shell script , answer accepted.

Java-

Boolean SubString(String str,String str1){
int j=0
for (int i=0;i<str.lenght();i++){

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

j++;
}
else{
j=0;
}
if(j==str1.length()){
return True;
}
}
return False;
}

Please comment in case of any error

int main()
{
	char string[] = "my name is megharaj I an from india";
	char *stringp = string;
	char sub[] = "an";
	int length = strlen(sub) -1;
	char *temp;
	while(*stringp != '\0') {
		temp = sub;
		length = 2;
		while((stringp != '\0') && (*stringp == *temp) && length > 0) {
			stringp++;
			temp++;
			length--;
			if(length == 0) {
				printf("substring found\n");
				return 0;
			}
		}
		stringp++;
	}
	printf("substring not found\n");
	return 0;
}

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

int main(){
char *s= malloc(50);
char *sub=malloc(5);
printf("Enter a string :\n");
fgets(s,40,stdin);
printf("Enter the sub string: \n");
fgets(sub,5,stdin);

char *temp=sub;
int count=0;

while(*s != '\0'){
         if(*sub==*s && sub != '\0'){
            count++;
            sub++;
            s++;
          }
         else if(count >strlen(temp) && *sub != *s && sub != '\0'){
              count--;
              sub--;
          }
         else{
            s++;
          }
      }

if(count==strlen(temp)){
     printf("Match found\n");
   }
else{
     printf("No match found\n");
   }

return 0;
}

public boolean checkSubstring(String subStr, String str)
{
int l=subStr.length();
int j=str.length();
for(int i=0;i<(j-l+1);i++)
{
String s=str.subString(i,i+l);
if(s.equals(subStr))
return true;
}
return false;
}