Нахождение последнего вхождения строки в предложении в C - PullRequest
Новая
       83

Нахождение последнего вхождения строки в предложении в C

0 голосов
/ 19 февраля 2020

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

Что я пробовал: я использовал указатели для хранения адресов заканчивается как предложения, так и слова, которое мы ищем. Затем я использовал while l oop, чтобы перебрать строку. Если текущий символ совпадает с последним символом слова, которое мы ищем, мы вводим другое, в то время как l oop, который сравнивает их. Если указатель, указывающий на начало слова, и тот, который мы использовали для итерации по слову, совпадают, слово найдено.

Вот некоторый код: 


#include <stdio.h>

int find_last( char *str,  char *word)
{
    char *p, *q;

    char *s, *t;

    p=str;                            /* Pointer p now points to the last character of the sentence*/
    while(*p!='\0') p++;
    p--;

    q = word;
    while(*q!='\0') q++;             /* Pointer q now points to the last character of the word*/
    q--;

    while(p != str) {
        if(*p == *q) {
            s=p;                        /* if a matching character is found, "s" and "t" are used to iterate through */
            /* the string and the word, respectively*/
            t=q;

            while(*s == *t) {
                s--;
                t--;
            }

            if(t == word-1) return s-str+1;  /* if pointer "t" is equal by address to pointer word-1, we have found our match. return s-str+1. */
        }
        p--;
    }
    return -1;
}

int main()
{
    char arr[] = "Today is a great day!";

    printf("%d", find_last(arr, "Today"));

    return 0;
}

Итак, этот код должен возвращать 0, но он возвращает -1.

Он работает во всех остальных случаях, которые я тестировал ! При запуске в CodeBlocks вывод будет таким, как и ожидалось (0), но при использовании любой другой онлайновой IDE я смог найти выход -1.

1 Ответ

1 голос
/ 19 февраля 2020

Для начала параметры функции должны иметь квалификатор const, а тип возврата должен быть либо size_t, либо ptrdiff_t.

Например, 

ptrdiff_t find_last( const char *str,  const char *word );

В любом случае функция должна быть объявлена ​​как минимум как 

int find_last( const char *str,  const char *word );

Функция должна эмулировать поведение стандартной C функции strstr. То есть, когда второй аргумент является пустой строкой, функция должна вернуть 0.

Если какой-либо из аргументов является пустой строкой, ваша функция имеет неопределенное поведение из-за этих операторов 

p=str;                            /* Pointer p now points to the last character of the sentence*/
while(*p!='\0') p++;
p--;
^^^^

q = word;
while(*q!='\0') q++;             /* Pointer q now points to the last character of the word*/
q--;
^^^^

Если строка, на которую указывает str, содержит только один символ, то ваша функция возвращает -1, потому что условие l oop

while(p != str) {

оценивается как ложное, независимо от того, равны ли обе строки друг другу или нет.

Этот l oop

        while(*s == *t) {
            s--;
            t--;
        }

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

И это оператор 

if(t == word-1) return s-str+1;

также может вызывать неопределенное поведение по той же причине.

Функция может быть определена так, как показано в демонстрационной программе ниже. 

#include <stdio.h>

int find_last( const char *str,  const char *word )
{

    const char *p = str;

    int found = !*word;

    if ( !found )
    {
        while ( *p ) ++p;

        const char *q = word;

        while ( *q ) ++q;

        while ( !found && !( p - str < q - word ) )
        {
            const char *s = p;
            const char *t = q;

            while ( t != word && *( s - 1 ) == *( t - 1) )
            {
                --s;
                --t;
            }

            found = t == word;

            if ( found ) p = s;
            else --p;
        }
    }

    return found ? p - str : -1; 
}

int main(void) 
{
    const char *str = "";
    const char *word = "";

    printf( "find_last( str, word ) == %d\n", find_last( str, word ) );

    word = "A";

    printf( "find_last( str, word ) == %d\n", find_last( str, word ) );

    str = "A";

    printf( "find_last( str, word ) == %d\n", find_last( str, word ) );

    str = "ABA";

    printf( "find_last( str, word ) == %d\n", find_last( str, word ) );

    str = "ABAB";

    printf( "find_last( str, word ) == %d\n", find_last( str, word ) );

    str = "ABCDEF";

    printf( "find_last( str, word ) == %d\n", find_last( str, word ) );

    str = "ABCDEF";
    word = "BC";

    printf( "find_last( str, word ) == %d\n", find_last( str, word ) );

    return 0;
}

Вывод программы 

find_last( str, word ) == 0
find_last( str, word ) == -1
find_last( str, word ) == 0
find_last( str, word ) == 2
find_last( str, word ) == 2
find_last( str, word ) == 0
find_last( str, word ) == 1
...