Больше Струны - strstr

Question

Так что я пытаюсь сделать свою собственную функцию strstr, со следующим: реализации внешних

char *mystrstr(char *haystack, char *needle); 
    // find the first occurrence of string needle 
    // in string haystack 
    // identical to strstr in <string.h> 
    // running time O(mystrlen(needle)*mystrlen(haystack)) 

Вот что у меня есть:

char *mystrstr(char *haystack, char *needle) 
{ 
if (haystack == needle) { return haystack; } 
int i = 0; int j = 0; 
while (haystack[i] != '\0') { 
    if (j == mystrlen(needle)) {return haystack + (i - mystrlen(needle)); } 
    if (haystack [i] == needle [j]) { 
    j++; i++; 
    } 
    else { j = 0; i++; } 

    } 
if (j == mystrlen(needle)) {return haystack + (i - mystrlen(needle)); } 
return NULL; 
} 

Моя проблема заключается в том, что, когда я set j = 0, я не хочу итерации i. Но в конце концов мне нужно повторить «i», чтобы вызвать разрыв цикла. Какие-либо предложения ?

Answer 1

Предполагая, что вы не хотите быть сложным (например, вариант Кнута-Морриса-Пратта или Бойер-Мура) Я думаю, что сделаю это, пройдя каждую возможную точку в «стоге сена» и сравняя N символов иглы до следующих N символов в стоге сена. Если они равны, вы нашли позицию.

Редактировать. В псевдо-коде, я бы сделал что-то вроде этого:

boolean check_pos check_for check_in 
    length = getlength(check_for) 
    for i = 1 to length 
     if (check_for[i] != check_in[i]) 
      return false 
end check_pos 

int my_strstr haystack needle 
    length = getlength(haystack) - getlength(needle) 

    for i = 1 to length 
     if (check_pos(needle, haystack+i) 
      return i 
    return -1 
end my_strstr 

Answer 2

Поскольку это домашнее задание, я просто укажу вам в правильном направлении, и вы сможете выяснить остальное. Вы проверяете нулевой ограничитель на одну строку, но не на другую.

Answer 3

дряблых на детали из-за домашнюю работу тег

вы хотите проходной стог, я = 0 до I = haystack.length с внутренний цикл, который делает j = 0 до j = длина иглы.

проверьте наличие сена [i + j] = игла [j], если нет, вы можете выйти из внутреннего цикла, это не соответствует. Затем вам нужно разработать способ проверки, если вы зациклились на всех иглах и таким образом нашли совпадение

Вам также необходимо убедиться, что вы не выходите за пределы (подсказка, состояние конца внешнего контура)

EDIT

Кроме того, не забывайте, что вы можете получить доступ к данным как массив

int i = 0; 
while(haystack[i] != \0){ 
    // do stuff 
    i++ 
} 

EDIT 2

Еще одна вещь, которую вам нужно запомнить, это то, что char* не является строкой, если две переменные типа char* одинаковы, это означает, что они являются одним и тем же указателем. Проверьте, что две строки стиля C одинаковы, вам нужно проверить каждый символ в последовательности.

Ваш внешний цикл должен пройти через первый символ haystack[0] и должен остановиться, как только он получит нулевой символ. который будет выглядеть как

int i = 0; 
while(haystack[i] != '\0'){ 
    // do stuff 
    i++; 
} 

вам также потребуется внутренний цикл, так что для каждого символа «стог» вы сравните, если вы можете работать через иглу и получить матч. Вы должны объявить встречное переменную перед вне цикла, но установить его в ноль перед каждый раз, когда внутренний цикл выполняется, так что теперь мы имеем

int i = 0; 
int j; 
while(haystack[i] != \0){ 
    j = 0; 
    while(needle[j] != '\0' && haystack[i + j] != '\0'){ 
     // noticed that we also check that we are not going out of bounds of haystack 
     // do stuff 
     j++; 
    } 
    i++; 
} 

точно, мы должны сравнить каждый символ, так что мы можем просто заменить // do stuff с хорошей проверкой, как if(needle[j] != haystack[i +j]){ // no match yet }.Теперь вам, вероятно, потребуется добавить несколько дополнительных вещей, чтобы отслеживать происходящее, что-то вроде логического «matchFound», которое объявляется перед внешним циклом и устанавливается как true перед внутренним циклом.

С этим булевым значением предполагается, Таким образом, после внутреннего цикла, но все еще находящегося вне цикла, мы можем добавить чек, например if(mathFound) { return i; }.

Должно быть ясно, что, когда мы проверяем символ иглы на один из стога сена, нам нужно установить «matchFound» в false, где комментарий // no match yet был. Я также предложил бы переместить && haystack[i + j] != '\0' во внутренний цикл и настроить таким образом, чтобы, если нашел нулевой байт для стога сена, он должен установить matchFound в false и выйти из внутреннего цикла.

Таким образом, из финалом код будет что-то вроде

int i = 0; 
int j; 
bool matchFound; 
while(haystack[i] != \0){ 
    j = 0; 
    matchFound = true; 
    while(needle[j] != '\0'){ 
     if(haystack[i + j] == '\0' || needle[j] != haystack[i+j]){ 
      // combined the out of bound check with the comparison 
      // note the out of bound check is first, try to think why 
      matchFound = false; 
      break; 
     } 
     j++; 
    } 
    if(matchfound){ 
     return i; 
    } 
    // Check first THEN increment i, what happens if we increment i first? 
    i++; 
} 

Это, вероятно, все еще нуждается в некоторые настройки, чтобы получить его работу, но вы должны получить много ближе к решению вас проблемы