Тестер анаграмм в C

В C строки представляют собой массивы char с завершающим нулем, то есть байт со значением 0, обычно представленный как '\0'. Вы не должны предполагать какую-либо конкретную длину, такую ​​как 100. Действительно, размер массива в аргументах прототипа функции игнорируется компилятором. Вы можете определить длину, просканировав нулевой терминатор, что эффективно делает strlen(), или вы можете написать код таким образом, чтобы избежать многократного сканирования, останавливаясь на нулевом терминаторе. Вы должны убедиться, что ваши функции работают с пустой строкой, которая представляет собой массив с одним нулевым байтом. Вот проблемы в вашем коде:

В функции noSpaces вы выполняете итерацию за концом строки, изменяя память, потенциально принадлежащую следующей строке. Программа имеет неопределенное поведение.

Вы должны остановиться в конце строки. Также используйте 2 переменные индекса для выполнения в линейном времени:

void noSpaces(char word[]) {
    /*
    This is a function to get rid of spaces in a word
    It does this by scanning for a space and shifting the
    array elements at indices > where the space is
    down by 1 as long as there is still a space
    there. 
    */
    int i, j;
    for (i = j = 0; word[i] != '\0'; i++) {
        if (word[i] != ' ') {
            word[j++] = word[i];
        }
    }
    word[j] = '\0';
}

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

int compare(const char word1[], const char word2[]) {
    /*
    This is a function that accepts two sorted 
    char arrays (see 'sortWords' below) and
    returns 1 if it finds a different character
    at entry i in either array, or 0 if at no 
    index the arrays have a different character.
    */
    for (int i = 0; word1[i] == word2[i]; i++) {
        if (word1[i]) == '\0')
            //printf("anagrams\n");
            return 0;
        }
    }
    // printf("not anagrams\n");
    return 1;
}

sortWords имеет неопределенное поведение для пустой строки, потому что вы читаете char по индексу 1 за концом массива. Вот исправленная версия:

void sortWords(char word[]) {
    /*
    This is a function to sort the input char arrays
    it's a simple bubble sort on the array elements.
    'sortWords' function accepts a char array and returns void,
    sorting the entries in alphabetical order
    being careful about ignoring the 'special character'
    '\0'.
    */
    for (int j = 0; word[j] != '\0'; j++) {
        for (int i = 1; i < j; i++) {
            if (word[i - 1] > word[i]) {
                char dummy = word[i - 1];
                word[i - 1] = word[i];
                word[i] = dummy;
            }
        }
    }
}

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

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

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

Вот прямой подход:

#include <stdio.h>

int check_anagrams(const char word1[], const char word2[]) {
    /*
       This function accepts two strings and returns 1 if they
       are anagrams of one another, ignoring spaces.
       The strings are not modified.
     */
    int i, j, len1, letters1, letters2;

    /* compute the length and number of letters of word1 */
    for (len1 = letters1 = 0; word1[len1] != '\0'; len1++) {
        if (word1[len1] != ' ')
            letters1++;
    }

    /* create a copy of word1 in automatic storage */
    char copy[len1];    /* this is an array, not a string */
    for (i = 0; i < len1; i++)
        copy[i] = word1[i];

    for (j = letters2 = 0; word2[j] != '\0'; j++) {
        char temp = word2[j];
        if (temp != ' ') {
            letters2++;
            for (i = 0; i < len1; i++) {
                if (copy[i] == temp) {
                    copy[i] = '\0';
                    break;
                }
            }
            if (i == len1) {
                /* letter was not found */
                return 0;
            }
        }
    }
    if (letters1 != letters2)
        return 0;
    return 1;
}

int main(int argc, char *argv[]) {
    const char *s1 = " listen";
    const char *s2 = "silent   ";
    if (argc >= 3) {
        s1 = argv[1];
        s2 = argv[2];
    }
    int result = check_anagrams(s1, s2);
    if (result == 0) {
        printf("\"%s\" and \"%s\" are not anagrams\n", s1, s2);
    } else {
        printf("\"%s\" and \"%s\" are anagrams\n", s1, s2);
    }
    return result;
}

Вы делаете логическую ошибку в своей вспомогательной функции. Вы начинаете копирование с word[j], а не с начала второго слова, поэтому вы собираетесь удалить столько начальных символов, сколько начальных пробелов, как вы видите в выводе.

Обратите внимание, что j=i и i подсчитывают количество начальных пробелов из внешнего цикла.

Кстати у вас должно получиться всего две петли. Поместите условие while в первый цикл for следующим образом: for (int i = 0; i<100 && word[i]==' '; i++).

Чтобы исправить вашу логическую ошибку, вам нужно использовать другой итератор k, инициализированный нулем в самом внутреннем цикле, и использовать word[k] = word[j+1]. Я думаю, это сработает.

У вас есть проблема с переполнением буфера для argv[1] и argv[2], если длина буфера argv[1] меньше 100. Поэтому я думаю, что вам следует использовать цикл for с strlen(word), этого достаточно. Когда вы используете статическую длину со 100 в цикле for, иногда слово получает данные из другого места памяти и делает вашу программу в неопределенном поведении. И другие функции имеют ту же проблему. Я имею в виду функции sortWords и compare.

Вот моя модификация в вашей функции noSpaces, она должна работать.

void noSpaces(char word [100]){
    /*
    This is a function to get rid of spaces in a word
    It does this by scanning for a space and shifting the
    array elements at indices > where the space is
    down by 1 as long as there is still a space
    there.
    */
    for(int i =0; i<strlen(word)-1; i++){
        while(word[i]==' '){
            for(int j = i ; j<strlen(word); j++){
                word[j] = word [j+1];
            }
        }
    }
}

Вместо того, чтобы пытаться удалить пробелы и отсортировать, что составляет O (N lg N) время выполнения. Вы можете выполнить операцию O(N), просто создав массив, представляющий количество каждой буквы в слове. И просто игнорируйте пробелы при этом.

// Iterate over each character in the string
// For each char in string, increment the count of that character
// in the lettercount array.
// Return the number of unfiltered letters that were counted
int fillLetterCountTable(const char* string, int* lettercount)
{
    int len = strlen(string);
    int valid = 0;

    for (int i = 0; i < len; i++)
    {
       unsigned char index = (unsigned char)(string1[i]);
       if (index ==  ' ')  // ignore spaces
       {
           continue;
       }
       counts[index] += 1;
       valid++;
    }

    return valid;
}

// compare if two strings are anagrams of each other
// return true if string1 and string2 are anagrams, false otherwise
bool compare(const char* string1, const char* string2)
{
    int lettercount1[256] = {0};
    int lettercount2[256] = {0};

    int valid1 = fillLetterCountTable(string1, lettercount1);
    int valid2 = fillLetterCountTable(string2, lettercount2);

    if (valid1 != valid2)
        return false;

    // memcmp(lettercount1, lettercount2, sizeof(lettercount1));
    for (int i = 0; i < 256; i++)
    {
        if (counts1[i] != counts2[i])
            return false;
    }
    return true;
}