计算字符串的频率 - 仅使用 stdio.h - C

Question

我们有一些 C 的练习（我们必须只使用 stdio.h 库）：

Write a function that receives two strings and returns the number of occurences of the second in the first one, there could be overlapping dependent on cyclic parameter.

但是我没有成功处理isCyclic打开的情况。

例如，如果 isCyclic 不是 0 并且：

char *str1 = "aaa"; char *str2 = "aa"; We have to return 3

我在 isCyclic 中的错误是什么？..

这是我的实现：

int strLength(const char *str) {
    int count = 0;

    while (*str) {
        count++;
        str++;
    }

    return count;
}

unsigned int countPatInStr(const char *str1, const char *str2, int isCyclic)
{
    int patternSize = strLength(str2);
    int textSize = strLength(str1);
    int res = 0;
    int j;

    if (isCyclic) { // Here is the case when overlapping is needed
        if (patternSize > textSize) {
            for (int i = 0; i < patternSize - textSize; i++) {
                for (int j = 0; j < textSize; j++) {
                    if (str1[j] != str2[i + j]) {
                        break;
                    }

                    if (j == textSize && i + j < patternSize) {
                        str2 += i + j;
                    } else if (j == textSize && i + j == patternSize) {
                        res++;
                    }
                }
            }
            return 0;
        }
    } else {
        /* A loop to slide pat[] one by one */
        for (int i = 0; i <= textSize - patternSize; i++) {
            /* For current index i, check for pattern match */
            for (j = 0; j < patternSize; j++) {
                if (str1[i + j] != str2[j]) {
                    break;
                }
            }

            // if pat[0...M-1] = txt[i, i+1, ...i+M-1]
            if (j == patternSize) {
                res++;
            }
        }
        return res;
    }

    return 0;
}

Answer 1

你的函数至少是无效的，因为在这个循环中

for (int i = 0; i < patternSize - textSize; i++)

条件可以等于假。所以循环永远不会执行。

在这个循环中

            for (int j = 0; j < textSize; j++) {
                if (str1[j] != str2[i + j]) {
                    break;
                }

当 isCyclic 为非零时，使用指针 str1 的索引 j 和指针 str2 的索引 i + j。

函数可以写得更简单，如下面的演示程序所示。

#include <stdio.h>

size_t strLength( const char *s )
{
    size_t n = 0;

    for ( ; *s; ++s ) ++n;

    return n;
}

size_t countPatInStr( const char *s1, const char *s2, _Bool isCyclic )
{
    size_t count = 0;

    size_t n1 = strLength( s1 );
    size_t n2 = strLength( s2 );


    if ( !( n1 < n2 ) || isCyclic )
    {
        size_t n = isCyclic ? n1 : n1 - n2 + 1;
        size_t divident = isCyclic ? n : n1;

        for ( size_t i = 0; i < n; i++ )
        {
            size_t j = 0;
            while ( j < n2 && s1[ ( i + j ) % divident] == s2[j] ) j++;

            count += j == n2;
        }
    }

    return count;
}

int main(void) 
{
    const char *s1 = "aaa";
    const char *s2 = "aa";

    printf( "%zu\n", countPatInStr( s1, s2, 0 ) );
    printf( "%zu\n", countPatInStr( s1, s2, 1 ) );

    return 0;
}

程序输出为

2
3

或者如果 s1 和 s2 定义为

const char *s1 = "aa";
const char *s2 = "aaa";

那么输出将是

0
2

或者如果它们被定义为

const char *s1 = "abcabc";
const char *s2 = "abc";

则输出为

2
2

是你需要的吗？

计算字符串的频率 - 仅使用 stdio.h - C

Count frequencies of string - using only stdio.h - C

c

substring

c-strings

char

cyclic