Проблема C внутри функции, которая ищет слово внутри другого и возвращает позицию

Question

Следующая проблема C ищет s1 внутри s2 и возвращает позицию, в которой s1 был найден в s2. я написал этот код, и он отлично работает для значений, таких как s1: car s2: carnal, но если у меня есть s1: car и s2: cbrcarnal, я думаю, что он входит в бесконечный цикл или что-то, но он ничего не отображает. проблема? это должно быть в моей функции. Ох, и мне не разрешено использовать strstr.

код:

#include "stdafx.h"
#include "stdio.h"
#include "string.h"

int subsir(char s1[],char s2[],int k)
{    int n,m,i=0,j,poz=-1;
n=strlen(s1);
m=strlen(s2);
if(n>m)
return -1;
j=k;
while(j<=m-n)
if((s1[i]==s2[j])&&(s1[n-1]==s2[j+n-1]))
{
    poz=j;
    while(j+1<poz+n-1)
        if(s1[i+1]==s2[j+1])
            {i++;
            j++;
            }
        else
            return subsir(s1,s2,poz++);
}
else
j++;

if(poz!=-1)
    return poz;
else
    return -1;
}

int _tmain(int argc, _TCHAR* argv[])
{char s1[30],s2[30];
int n;
printf("introduceti sirul 1: ");
scanf("%s",&s1);
printf("introduceti sirul 2: ");
scanf("%s",&s2);
n=subsir(s1,s2,0);
if(n!=-1)
    printf("%s is found in %s, at: %d\n",s1,s2,n);
else
    printf("s %s is not found in %s\n",s1,s2);

}

Answer 1

Вот отформатированная версия вашего кода. Единственными изменениями, которые я сделал, были комментарии, фигурные скобки, пробелы, объявление переменных ближе к месту их использования, изменение цикла while в цикл for и удаление неэффективного постинкремента. Это точно так же, как ваш код:

int subsir(char s1[], char s2[], int k) {
    // Return location of s1 in s2, starting at index k in s2.

    int n = strlen(s1);
    int m = strlen(s2);
    if (n > m)  // s1 cannot be in s2
        return -1;

    int poz = -1;
    for (int j = k, i = 0; j <= m - n;) {
        // if first and last character in s1 match corresponding locations in s2
        if((s1[i] == s2[j]) && (s1[n - 1] == s2[j + n - 1])) {
            // save current s2 location in poz
            poz = j;
            while (j + 1 < poz + n - 1) {
                if(s1[i + 1] == s2[j + 1]) {
                    i++;
                    j++;
                }
                else {
                    return subsir(s1, s2, poz);
                }
            }
        }
        else {
            j++;
        }
    }

    return poz;
}

В этой версии вам будет гораздо легче обнаружить проблемы:

• Я знаю, что вы имели это в виду и либо записали где-то явно (или вы просто читали из описания задания), но это всегда помогает вашему мыслительному процессу включить короткое предложение о цель функции. Это первый комментарий.

• Обычно я не включаю второй и третий комментарии в мой код, но я пишу для другой аудитории, чем вы. Объяснение «почему» (для второго комментария) и как работают более сложные выражения (для третьего комментария) должно помочь вам.

• Четвертый комментарий является началом определения роли, которую выполняет поз. Вы должны быть в состоянии заявить, подобно короткому описанию функции, короткую рекламу о каждой переменной. Обычно, например, для переменных n, m, k, j и i, вам не нужно явно указывать это в коде - но если вы запутались, начните добавлять их. Например, «k - начальный индекс для поиска», «n - длина s1», «j и i -« текущие »местоположения в s2 и s1 соответственно» и т. Д.

• Постинкремент, который я удалил, был в операторе return, но, поскольку элемент управления никогда не возвращается к этой функции (и, следовательно, poz больше никогда не используется), он не влияет.

• Вы проверили, было ли poz -1, и если это было, вернул -1; в противном случае возвращается поз. Это то же самое, что возвращать поз напрямую.

• Вы модифицируете i, но если управление выходит из цикла while, вы никогда не обнуляете его; таким образом, вы никогда не начнете поиск с начала s1 с этого момента.

• Поскольку вы начинаете с poz (вместо poz + 1) при рекурсивном вызове, вы застреваете в цикле, постоянно проверяя одно и то же местоположение снова и снова. (Передача поз + 1 исправляет это.)

Чтобы продолжить отсюда, я бы преобразовал ваш внутренний цикл в отдельную функцию, выполняющую эквивалент strncmp - или использовал бы strncmp напрямую, если вы можете. Большая модульность облегчает решение проблем.

Рекурсия здесь не нужна, но можно смоделировать проблему таким образом:

• если s1 находится в s2, начиная с позиции k, вернуть k
• иначе вызовите subsir (s1, s2, k + 1) для поиска в следующем месте
  • это обычно делается в цикле, а не в рекурсивном вызове, но с оптимизацией хвостового вызова это точно то же самое

Answer 2

Ваш код ооочень сложен ... Честно говоря, мне не хочется внимательно на него смотреть. Но я хотел бы показать вам, как я это сделаю

int search(char* what, char* where)
{
   int whatlen = strlen(what);
   int wherelen = strlen(where);
   for(int i = 0; i <= wherelen - whatlen; ++i)
   {
      int j;
      for(j = 0; j < whatlen; ++j)
      {
          if(what[j] != where[i+j])
             break;
      }
      if(j == whatlen)
         return i;
   }
   return -1;
}

Answer 3

Я думаю, проблема в том, что вы не используете strstr.