CareerCup

Strange that none so far mentioned about KMP algorithm. This is a classic case of Knuth-Morris-Pratt algorithm. Check wiki for more details.
Rabin-Karp is too heavy for this.

2nd string is the sub-string of 1st string. For getting the position from where 2nd string start.
in java
here i am taking 1st string as a and 2nd string as b.

a=o.readLine();a=a.trin(); // taking input of 1st string
b=o.readLine();b=b.trim(); // taking input of 2nd string
String c=b.substring(0,1); // find the first word of 2nd strig
Int i=a.indexOf('c'); // finding the index from where 2nd string start in the 1st string

Try Rabin-Karp

int findPosition(String S1, String S2)
{
int i=0;
int j;
for(j=0;j< S1.length();j++){

char tempchar= S2.charAt(i);
if(tempchar==S1.charAt(j)){
i++;
if(i==S2.length()){
break;
}
}
else { i=0; }


}

if(i==S2.length()){
j=j-S2.length()+1;
}
else j=0;
return j;
}

#include<stdio.h>
#include<string.h>
int main()
{
	char str1[10000];
	char str2[10000];
	int arr[100000];
	int i,j,k1,k2,temp=0,position,k,t=0;
	scanf("%s",str1);
	scanf("%s",str2);
	k1=strlen(str1);
	k2=strlen(str2);
	for(i=0;i<k1;i++)
	{
		temp=0;
		if(str1[i]==str2[0])
		{
			temp=temp+1;
			position=i;
			k=i+1;
			for(j=1;j<k2;j++)
			{
				if(str1[k]==str2[j]){
				temp=temp+1;
				k=k+1;
				}
				else{
				break;
				}
				
			}
		}
		if(temp==k2)
		{
			arr[t]=position+1;
			
			t=t+1;
		}
	}
	for(i=0;i<t;i++)
	{
		printf("%d ",arr[i]);
	}
	return 0;
}

/*
1. Start from the end of both strings
2. compare last element of str2 with str1
- if matches compare next element from last and so on
-if str2 start is reached return Str1 current position
- if doesnt match start comparing str2's last element and Str1 current element
*/

bool CheckSubString(char * Str1, char * Str2, int len1, int len2)
{
	int last1 = len1 - 1;
	int last2 = len2 - 1;
	int i = last1;
	int j = last2;

	if(len1 < len2)
	{
		return -1;
	}

	while(i >= 0 && j >= 0)
	{
		if(Str1[i] == Str2[j])
		{
			i--;
			j--;
			continue;
		}
		else
		{
			j = last2;
			i--;
		}
	
	}
	if(j == -1)
	{
		return (i+1);
	}

	return -1;
}

int StringMatch(string& A, string& B) 
{
   
	for(int i=0; i< A.size(); i++)
	{
		int j=0;

		if(A[i] == B[0])
			for(; j<B.size(); j++)
			{
				if((j+i) >= A.size())
					break;
				if(A[j+i] != B[j])
					break;
			}
			if(j == B.size())
				return i;
			i += j; 
	}
	return -1;
}

sort the given array
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
swap(a[j],a[i]);
print(a);
swap(a[j],a[i])
}
please tell me i m doing it right or wrong

sort the given array
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
swap(a[j],a[i]);
print(a);
swap(a[j],a[i])
}
please tell me i m doing it right or wrong

sort the given array
for(i=1;i<n;i++)
for(j=0;j<i;j++)
{
swap(a[j],a[i]);
print(a);
swap(a[j],a[i])
}
please tell me i m doing it right or wrong

rabin karp
or
boyer moore
or
KMP will b the answers...

if iam taking string objects cann't i use find function in <string>
str.find(str1)

I can not tell the exact algorithm, but I am sure that if you build a suffix tree, which can be done on linear time, then checking if the second string is in the tree is also linear and as far as I remember it was very easy to get the node of the tree which points to the start of the string.

this is one approach, but I am looking for something better. the complexity for this algorithm is O(m+n) in best case and O(nm) worst case

simply try to trace the string, as soon as found the first match character start comparing with pattern. If matched report the start character position, otherwise continue from next character of first start matched in last step.

int findStr(char *str, char *pattern)
{
	int i=0, j=0, ptr=0;
	for(; i<strlen(str)-strlen(pattern);)
	{
		while(*(pattern+j)==*(str+i))
		{ 
			i++; 
			j++; 
		}
		if(*(pattern+j)=='\0')
			return ptr;
		j=0;
		i=++ptr;
	}
	return -1;
}