CareerCup

(Look at the interface for strtok_r.)

My idea is:
O(n^2) solution is the straight forward function.
O(n) solution is doing the comparison of "check sums" before matching the token.
It is kind of "hashing" trick....

I think it works....

<pre lang="" line="1" title="CodeMonkey94889" class="run-this">// the first trivial solution
// return 0 as false, non-zero as true
int isMatch (char *start, char *pattern, int l_start. int l_pattern) {
if (l_start < l_pattern) return 0;
for (int i = 0 ; i < l_pattern ; i++) {
if (start[i] != pattern[i]) return 0;
return 1;
}

char *strtok(char *s_input, char *token) {
static char *next = NULL;
static int l_total;
static int i_curr;
if (token == NULL) {
next = s_input;
return NULL;
}

char *retS = NULL;
int l_token = strlen(token);
if (i_curr == l_total) return NULL;
else if ((i_curr+l_token) <= l_total) {
int len = 0;
while (i_curr + len < l_total) {
if (isMatch(s_input[i_curr+len], token, l_total-i_curr-len, l_token) != 0) {
if (len == 0) return "";
retS = (char*)malloc(sizeof(char)*len);
strncpy(retS, &s_input[i_curr], len);
i_curr += (len + l_token);
}
len++;
}
}

i_curr = l_total;
retS = (char*)malloc(sizeof(char)*(l_total-i_curr));
strncpy(retS, &s_input[i_curr], l_total-i_curr);
return retS;
}


// this is the O(n) solution
char *strtok(char *s_input, char *token) {
static char *next = NULL;
static int l_total;
static int i_curr;
if (token == NULL) {
next = s_input;
return NULL;
}

char *retS = NULL;
int l_token = strlen(token);
if (i_curr == l_total) return NULL;

// calculate the hash number of the token
int h_token = 0;
for (int i = 0 ; i < l_token ; i++)
h_token += (int)token[i];

if ((i_curr+l_token) <= l_total) {
int curr_hash = 0;
for (int i = 0 ; i < l_token ; i++)
curr_hash += (int)s_input[i_curr+i];

int len = 0;
while (i_curr + len < l_total) {
if (curr_hash == h_token) {
if (isMatch(s_input[i_curr+len], token, l_total-i_curr-len, l_token) != 0) {
if (len == 0) return "";
retS = (char*)malloc(sizeof(char)*len);
strncpy(retS, &s_input[i_curr], len);
i_curr += (len + l_token);
}
}
else if (i_curr+len+1 < l_total) {
curr_hash -= (int)s_input[i_curr+len];
len++;
curr_hash += (int)s_input[i_curr+len+l_token];
}
}
}

i_curr = l_total;
retS = (char*)malloc(sizeof(char)*(l_total-i_curr));
strncpy(retS, &s_input[i_curr], l_total-i_curr);
return retS;
}
</pre><pre title="CodeMonkey94889" input="yes">Here is the code....</pre>

Hey can we use prime numbers..?
assign unique prime numbers to all the delimiters ...and take there product..

iterate through the string and take mod with every character if the mod is zero..u have your substring..

correct me if m wrong