Больше строк - 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;
}  

Моя проблема в том, что когда я устанавливаю j = 0, я не хочу повторять 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

Не вдаваясь в детали, из-за тега домашней работы

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

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

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

РЕДАКТИРОВАТЬ

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

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

РЕДАКТИРОВАТЬ 2

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

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

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

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

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 перед внутренним циклом.

При использовании этого логического значения предполагается, что если после внутреннего цикла оно все еще истинно, то совпадение найдено, и строка, на которую ссылается «needle», находится в «стоге сена» и начинается с i.Таким образом, после внутреннего цикла, но все еще в цикле out, мы можем добавить проверку вроде 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++;
}

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

Answer 3

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