CareerCup

# include <stdio.h>
#include <iostream>
using namespace std;
int strcspn(char* source, char* search)
{
int index[256];
for(int i=0;i<256;i++)
index[i]=0;
char* ptr=source;
int idx=0;
while(ptr[idx])
{
if(!index[ptr[idx]])
index[ptr[idx]]=idx;
idx++;
}
ptr=search;
idx=0;
while(ptr[idx])
{
if(index[ptr[idx]])
return index[ptr[idx]];
idx++;
}
return -1;
}

Just use strchr

size_t strcspn(const char *s1, const char *s2)
{
size_t ret=0;
while(*s1){
if(strchr(s2,*s1)){
return ret;
else
s1++,ret++;
}
}
return ret;
}

and strchr is essentially

char *strchr(const char *s, int c)
{
while (*s != (char)c)
if (!*s++)return 0;

return (char *)s;
}

my Ans is Place source string in hash and then look for search string in that hash.

really nice

I am not able to follow winia's algo..
Can anybody explain??

if run this program, you'll get the result 2. I think the question has a probelm.

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

int main()
{
char* source = "ttbbcca";
char* search = "ggabba";

printf("result = %d\n", strcspn(source, search));

return 0;
}

in the manual, the explanation is like below:
size_t strcspn (const char *string, const char *stopset) [Function]
The strcspn (\string complement span") function returns the length of the initial substring of string that consists entirely of characters that are not members of the set specied by the string stopset. (In other words, it returns the offset of the first character in string that is a member of the set stopset.)
For example,
strcspn ("hello, world", " \t\n,.;!?")
-> 5

So, here, we can see that the result should be 2 because the first character which is one of the string 'search' is b.

anyway, for this question, my answer is like this:

int strcspn(char* source, char* search)
{
int i;
int z_iArrRes[26];

for ( i = 0; i < 26; ++i )
z_iArrRes[i] = -1;

for ( i = 0; i < strlen(source); ++i )
if ( z_iArrRes[*(source + i) - 'a'] == -1 )
z_iArrRes[*(source + i) - 'a'] = i;
for ( i = 0; i < strlen(search); ++i )
if ( z_iArrRes[*(search + i) - 'a'] != -1 )
return z_iArrRes[*(search + i) - 'a'];

return -1;
}

int returnindex(char* string1, char* string2)
{
int hash[255]={0};
int l1=strlen(string1),l2=strlen(string2);
for(int ix=0;ix<l1;++ix)
{
if(!hash[string1[ix]])
{
hash[string1[ix]]=1;
for(int iy=0;iy<l2;++iy)
{
if(string1[ix]==string2[iy])
return ix+1;
}
}
}

}

btw I think you are looking for strspn.

strcspn computes the length of the maximum initial segment of the string pointed to by s1 which consists entirely of characters NOT from the string pointed to by s2.

In that case it's

size_t strspn(const char *s1, const char *s2)
{
size_t ret=0;
while(*s1 && strchr(s2,*s1++)) ret++;
return ret;
}

Why cant one just compare individual char locations in the source string and search string, then return the index if the characters at the same index match? Isnt this effecient? Am I missing something?

int strcspn(char* source, char* search) {
char hash[256];
for (int i=0; i<256; i++) hash[i] = 0;

char* ptr = source;
while(*ptr) {
hash[*ptr]=(!hash[*ptr])?ptr-source:hash[*ptr];
ptr++;
}
ptr = search;
while(*ptr) {
if (hash[*ptr]) return hash[*ptr];
ptr++;
}
return -1;
}

I guess the question framed is right! We need to keep the index values of each character in search string and check for the earliest occurence of the character in search string in the source string.

#include <iostream>
using namespace std;

int main(){

	char* source = "abbbbbbkjdfkd";
	char* search = "dkdkkl";

	int arr[256]; // To store the indices of all the search literals
	int ans = -1; // The least index of the search literal
	int index; // The final answer
	
	// Initialize all the array values to -1
	for(int i=0;i < 256; i++){
		arr[i] = -1;
	}

	// Based on the ASCII value put the index of the character in arr.
	for(int i=0; search[i]; i++){
		if(arr[search[i]] == -1) // Takes note of the first occurence of the character and ignores repetition
			arr[search[i]] = i;
			
	}
	
	//Scan the source array and update the index based on the character index
	for(int i=0; source[i]; i++){
		if(ans == -1 && arr[source[i]] != -1){
			index = i;
			ans = arr[source[i]];
		}
		else if(ans > arr[source[i]] && arr[source[i]] != -1){
			index = i;
			ans = arr[source[i]];
		}
	}
	cout << index;
	
	
	return 0;
}

We can build a BST from the source string with a slight modification that each node in the BST also record its index in the source str

We then search each char of the search str in the BST, and return the index if we find a match

total time is O(nlogn)