Более оптимизированное решение, найти количество подстрок в строке.Используя C

Question

Итак, у меня есть задача найти количество подстрок в данной строке. Я не могу использовать библиотеки C для выполнения этой задачи. stringExist может иметь только 2 строки в качестве параметров.

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

#include <stdio.h>

int stringExist(char string[], char s2[]);

int main(void){
    char string[] = "strstrASDstrSTRst";
    char s2[] = "str";
    printf("Final result: %i\n",stringExist(string,s2));
    return 0;
}

int stringExist(char string[], char s2[]){
/* I am aware that I can init all this values in one row */
    int count = 0;
    int size = 0;
    int i = 0;
    int temp = 0;
    int result = 0;

    while(s2[size]!='\0'){        
        size++;
    }

    while(string[i]!='\0')
    {        
        if(string[i]==s2[0])
        {
            printf("Found first occurrence\n");
            count=0;            
            while((temp=(string[i]==s2[count]))!=0)
            {            
                count++;                    
                if(size==count){
                    printf("Match\n");
                    result++;                    
                    break;                    
                }
                i++;
            }
        }
        i++;
    }


    return result;
} 

Решение № 2:

Пока ошибок не найдено.

Сделал немного другой обход строк, теперь я не увеличиваю i в цикле сравнения символов.

#include <stdio.h>

int stringExist(char string[], char s2[]);

int main(void){
    char string[] = "bobobobojkhhkjjkhbo;klkl;bobo";
    char s2[] = "bobo";
    printf("Final result: %i\n",stringExist(string,s2));
    return 0;
}

int stringExist(char string[], char s2[]){
    int count = 0;
    int size = 0;
    int i = 0;
    int c = 0;
    int temp = 0;
    int result = 0;

    while(s2[size]!='\0'){      
        size++;
    }
    for(i=0;string[i]!='\0';i++){
        if(string[i]==s2[0])
        {
            printf("Found first occurence at %i\n",i);
            count = 0;
            c = i;              

                while((temp=(string[c]==s2[count]))!=0)
                {       
                    printf("Count %i, I %i, current char: %c\n",count, c,string[c]);
                    count++;                    
                    if(size==count){
                        printf("Match\n");
                        result++;                   
                        break;                  
                    }
                    c++;
                }

        }
    }


    return result;
}

Спасибо за ваши предложения, Виталий

Answer 1

разбить его: (также работает для дополнительного условия)

int stringExist( char *string, char *sub )
{
  int count = 0;

  while( *string )
  {
    char *a = string, *b = sub;
    while( *a && *a == *b ) {a++;b++;}
    count += !*b;
    ++string;
  }

  return count;
}

Answer 2

Я предлагаю написать это так, как если бы вам было разрешено использовать библиотечные функции.Затем вернитесь и напишите свои собственные версии тех библиотечных функций, которые вы использовали.Хотя написание высокооптимизированных версий функций string.h может быть затруднено, написание приличных версий большинства из них на языке C довольно просто.

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

x = stringExist("aaaaa", "aa");

В строке "aaaaa" есть 4 вхождения строки "aa", но я недумаю, что ваша функция найдет их всех.Причина этого заключается в том, что при поиске по вхождению большей строки для вхождений секунды вы используете один и тот же индекс как для начала строки, так и внутри строки.На самом деле, похоже, что вы получите неправильные результаты для:

x = stringExist("tBatBath", "tBath");

Если, конечно, я неправильно понял, что должна была делать функция.

Если бы вы написаливаша собственная версия функции сравнения строкового префикса (по сути memcmp или strncmp), тогда вы бы отделили задачу сопоставления длины строки от более глубокого взгляда на строку и, вероятно, не допустили бы такой ошибки.

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

Answer 3

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

У вас может быть небольшая проблема: в такой строке, как "хахахаха", сколько раз должно быть обнаружено "хаха"? Дважды? Трижды? Ваш код будет видеть его дважды.

С стилистической точки зрения, безусловно, есть место для улучшений, но вы узнаете об этом со временем из кодирования и чтения кода другого =) Продолжай!

Answer 4

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

Сколько раз слово «bobo» появляется в строке «bobobo». Вероятно, должно быть вдвое больше, и я думаю, что ваш код как есть будет только один.

Удачи, Mark.