Подсчитать количество подстрок, имеющих только гласные

Question

Я написал код для поиска подстрок гласной данной подстроки. но мне нужна помощь в подсчете сформированной подстроки?

код:

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

bool isVowel(char c) {
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

void substr(char str[], int low, int high)
{
    printf("%.*s \n\n", high-low+1, (str+low));
}

int main(int argc, const char *argv[]) {

    char str[] = "aeixae";

    int length = strlen(str);

    int start_index = 0, end_index = 0;

    for (int x=0; x<=length; x++) {
        if (x == length || !isVowel(str[x])) {
            end_index = x;
            substr(str, start_index, end_index - 1 );
            start_index = end_index + 1;
        }

    }
    return 0;
} 

Answer 1

IMO есть гораздо больше подстрок.

Здесь у вас есть "грубая наивная" версия:

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

bool isVowel(char c) {
    return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
}

bool onlyVovels(const char *p1, const char *p2)
{
    while(p1 <= p2) 
    {
        if(!isVowel(*p1++)) return false;
    }
    return true;
}

void printSubstr(const char *start, const char *end)
{
    while(start <= end) putchar(*start++);
    putchar('\n');
}


int countAndPrint(const char *str)
{
    int count = 0;
    const char *start = str, *end = str;

    if(str && *str)
    {
        while(*++end);end--;
        for(start = str; start <= end; start++)
        {
            for(const char *cend = start; cend <= end; cend++)
            {
                if(onlyVovels(start, cend)) 
                {
                    printSubstr(start, cend);
                    count++;
                }
            }
        }
    }
    return count;
}


int main(int argc, char **argv)
{
    if(argc > 1)
    {
        printf("Number of vovel only substrings: %d\n", countAndPrint(argv[1]));
    }
}

https://godbolt.org/z/DiK_MV

Answer 2

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

Например:

Давайте возьмем aeixae. Наш текущий для переменной l oop i равен 0. (Подстроки, которые необходимо рассмотреть, помечены - строками).

a e i x a e

-

• Здесь start_index равно 0. Таким образом, число равно i - start_index + 1 (+1 также включает гласный из одного символа, так как он является подстрокой длины 1)

• i становится 1 в следующей итерации. Теперь мы будем рассматривать подстроки следующим образом:

a e i x a e

  -
---

• Итак, мы добавляем 2 к счету, поскольку у нас есть 2 гласные только для подстрок.
• i становится 2 в следующей итерации. Подстроки, которые необходимо рассмотреть:

a e i x a e
    -
  ---
-----

• Теперь, когда i становится 3, мы получаем x символ для обработки, который является не гласная. Итак, мы просто сбросили start_index на -1, так как теперь он разорвал цепочку. Вычисление продолжается для остальной части строки таким же образом.

Фрагмент:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <ctype.h>

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

long long int countAndPrint(const char *str)
{
    long long int count = 0,i;
    int len = strlen(str);
    int start_index = -1;
    for(i=0;i<len;++i){
        char c = tolower(str[i]);
        if(isVowel(c)){
            if(start_index == -1) start_index = i;
        }else{
            start_index = -1;
        }

        if(start_index != -1) count += (long long int)(i - start_index + 1);
    }    
    return count;
}


int main()
{
    printf("Number of vowel only substrings: %lld\n", countAndPrint("aeixae"));
}

Демонстрация: https://ideone.com/RKhjR7

• Сложность времени O (n) , сложность пространства O (1) .

Answer 3

Вот и вы.

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

bool isVowel( char  c) 
{
    const char *vowels = "aeiou";

    return strchr( vowels, c ) != NULL;
}

void output_substring( const char *s, int n )
{
    printf( "%*.*s\n", n, n, s );
}

int main(void) 
{
    char s[] = "aeixae";
    size_t count = 0;

    for ( const char *p = s; *p != '\0'; )
    {
        while ( *p != '\0' && !isVowel( *p ) ) ++p;

        if ( *p != '\0' )
        {
            ++count;
            const char *q = p;

            while ( *p != '\0' && isVowel( *p ) ) ++p;

            output_substring( q, p - q );
        }
    }

    printf( "There are %zu substrings\n", count );

    return 0;
}

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

aei
ae
There are 2 substrings

Другой подход заключается в использовании стандартных C функций strcspn и strspn вместо ; loop.

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

void output_substring( const char *s, int n )
{
    printf( "%*.*s\n", n, n, s );
}

int main(void) 
{
    char s[] = "aeixae";
    size_t count = 0;
    const char *vowels = "aeiou";

    for ( const char *p = s; *p != '\0'; )
    {
        p += strcspn( p, vowels );

        if ( *p != '\0' )
        {
            ++count;
            const char *q = p;

            p += strspn( p, vowels );

            output_substring( q, p - q );
        }
    }

    printf( "There are %zu substrings\n", count );

    return 0;
}

Вывод программы такой же, как показано выше.