C - проверить, является ли строка подстрокой другой строки

Question

Мне нужно написать программу, которая принимает две строки в качестве аргументов и проверить, является ли вторая подстрока первой. Мне нужно сделать это без использования каких-либо специальных библиотечных функций. Я создал эту реализацию, но я думаю, что она всегда возвращает true, если есть одна буква, которая одинакова в обеих строках. Можете ли вы помочь мне здесь. Я не уверен, что я делаю неправильно:

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

int my_strstr( char const *s, char const *sub ) {
    char const *ret = sub;

    int r = 0;
    while ( ret = strchr( ret, *sub ) ) {
        if ( strcmp( ++ret, sub+1 ) == 0 ){
            r = 1;
        }
        else{
            r = 0;
        }        
    }
    return r;
}

int main(int argc, char **argv){

    if (argc != 3) {
        printf ("Usage: check <string one> <string two>\n");
    }
    int result = my_strstr(argv[1], argv[2]);

    if(result == 1){
        printf("%s is a substring of %s\n", argv[2], argv[1]);
    } else{
        printf("%s is not a substring of %s\n", argv[2], argv[1]);
    }
    return 0;
}

Answer 1

Ваш подход к написанию strstr в корне ошибочен. Давайте посмотрим на то, что вы написали:

char const *ret = sub;

int r = 0;
while ( ret = strchr( ret, *sub ) ) {
    if ( strcmp( ++ret, sub+1 ) == 0 ){
        r = 1;
    }
    else{
        r = 0;
    }        
}
return r;

Прежде всего, поскольку вы инициализируете ret для указания на sub, вы сравниваете sub с самим собой и никогда не смотрите на s. Но давайте предположим, что вы хотели инициализировать ret значением s ...

ret = strchr( ret, *sub ) находит позицию следующего символа sub в пределах ret, а затем продвигается ret, чтобы начать с этого символа.

Затем вы выполняете strcmp( ++ret, sub+1 ), который определяет, равна ли строка, начинающаяся со следующего символа ret, строке, начинающейся со следующего символа sub, а затем продвигается ret, чтобы начать со следующего символ (независимо от того, был ли тест истинным или ложным).

Очевидно, что эта логика не делает то, что вы хотите. Что он на самом деле сделает, так это определит, равна ли подстрока строке s или находится в end строки s и не содержит повторяющихся букв.

Вот общее описание алгоритма, который вы хотите:

1. Найти позицию первого символа sub в s. Если не найдено, верните false.
2. Обновите s, чтобы оно начиналось с этой позиции
3. Предполагая, что длина sub равна n, проверьте, совпадают ли первые n символы s с sub (будьте осторожны, чтобы не пропустить конец s). Если это так, верните истину. В противном случае, передвиньте s на один символ и выполните цикл.

Обратите внимание, что вы никогда не должны искать какой-либо символ в sub, кроме первого. Идея состоит в том, чтобы использовать первый символ sub, чтобы найти потенциал начальных позиций для sub в s, а затем проверить, существует ли на самом деле подстрока sub. Если его там нет, вы хотите сбросить всю сумму s до этой точки, а затем начать сначала, пытаясь найти следующую потенциальную стартовую позицию.

Answer 2

Ну, вы не должны изменять ret в my_strstr. И strcmp не сравнивает подстроки, он сравнивает строки. Вы, вероятно, хотите использовать strncmp.

Answer 3

char const *ret = sub;

int r = 0;
while ( ret = strchr( ret, *sub ) ) {

ret хранит адрес подмассива и в в то время как заявление strchr(ret,*sub) сравнение значения в sub с адресом, хранящимся в ret будет ли это работать или нет (это сравнение правильно или нет) ответьте кто-нибудь, пожалуйста ...

Answer 4

Это может помочь разбить эту задачу немного по-другому. Эта задача состоит из двух ключевых частей: 1) найти начальную точку возможных совпадений подстрок и 2) проверить, является ли эта начальная точка действительно совпадающей подстрокой. Поэтому реализуйте это как две функции.

Сначала создайте функцию, которая определяет, являются ли две строки одинаковыми. Это должно быть относительно легко для кодирования, просто сравните первую букву с первой буквой, вторую со второй и т. Д. Если вы найдете две не соответствующие, верните false. Если вы дойдете до конца одной из строк, верните true. Если вам разрешено использовать strncmp, тогда это будет просто (strncmp(a, b, strlen(b)) == 0) (при условии, что b всегда является более короткой строкой).

Во-вторых, создайте функцию, которая перебирает строку, ища определенную букву. Всякий раз, когда он находит эту букву, он вызывает функцию и передает указатель на эту букву в строке. Другими словами, если вы вызвали my_function("This is a sample string", 's'), то функция должна пройти по строке, найти все четыре экземпляра буквы 's' и вызвать функцию, используя указатель на эту букву в строке. В этом случае функция, которую вы вызовете, - это функция, описанная в предыдущем абзаце.

Используя эту разбивку, вы вернете «true», как только любой из вызовов этой подфункции вернет «true», или вы вернете «false», если дойдете до конца входной строки. 1011 *

Answer 5

Когда

ret = strchr( ret, *sub )

встречается впервые, ret == sub. Так, strchr(ret, *sub) ищет первое вхождение первого символа ret в ret. Который вернет ret.

Итак, ret остается без изменений.

Далее

strcmp( ++ret, sub+1 ) == 0 

ret по-прежнему равен sub, поэтому приведенное выше утверждение равно true .

И вы получите 1 в качестве возврата.

Answer 6

Похоже, вы ищете char * sub в char * sub:

int my_strstr( char const *s, char const *sub ) {
char const *ret = sub;

Разве вы не должны устанавливать ret в s?

Также strcmp сравнивает строки, а не подстроки, поэтому strcmp ("abcde", "abc") возвращает false. Возможно, вам нужен strncmp, который также принимает целое число, определяющее длину.