无需包含即可编写代码的可能性<string.h>

Question

我编写了一段代码，它定义了一个带签名的函数，并采用 2 个参数 C，它从第一个参数的 0 返回一个数字 - 如果第二个参数包含第一个参数或 - 1。

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

int str_find(char* needle, char* haystack) {
    int needle_length = strlen(needle);
    int haystack_length = strlen(haystack);

    if (needle_length == 0) {
        return 0;
    }

    if (haystack_length == 0) {
        return -1;
    }

    int par_1 = 0;

    for(int par_2 = 0; par_2 < haystack_length; par_2++) {
        if (haystack[par_2] == needle[0]) {
            for (par_1 = 0; par_1 < needle_length; par_1++)
                if (haystack[par_2 + par_1])
                    break;
            if (par_2 == needle_length)
                return par_2;
        }
    }

    return -1;
}

int main()
{
    printf("%d\n",str_find("=","-h=123"));
    return 0;
}

是否有可能/如何在不使用

<string.h>

库的情况下编写此代码？

Answer 1

如果干草堆有几GB，为什么要简单地遍历它来确定上限？仅遍历干草堆一次（或更少）...

小挑战是玩代码的好机会：

#include <stdio.h>

int str_find( char* needle, char* haystack) {
    size_t i = 0, matched = 0;

    while( haystack[ i ] && needle[matched] )
        if( needle[ matched ] == haystack[i] )
            matched++, i++;
        else if( matched )
            i -= matched - 1, matched = 0; // rewind a bit and try again
        else i++;

    return needle[matched] == '\0' ? i - matched : -1;
}

int main(void ) {

    char *hay = "longlongagoinagalaxyfarfarawaygeorgelucasmadeababananana";

    char *needles[] = { "far", "lucas", "yoda", "force", "banana" };

    for( int i = 0; i < sizeof needles/sizeof needles[0]; i++ )
        printf( "%s - %sfound\n", needles[i], str_find( needles[i], hay ) < 0 ? "not " : "" );

    return 0;
}

输出：

far - found
lucas - found
yoda - not found
force - not found
banana - found

---

大海捞针全部找到：
这一挑战不是简单地找到/未找到，而是表明找到任何针的多个实例（或没有找到任何针），因此值得更多开发。

在这里，

str_find()

的返回得到了更多的利用，并且

main()

所做的测试变得更加详细。

此代码不会阻止搜索零长度针。如果有人可以描述零长度针的样子，我将不胜感激在评论中阅读它。

#include <stdio.h>

char *str_find( char *needle, char *haystack ) { // change signature

    /* body same as above, but return statement changed */

    return needle[ matched ] ? NULL : haystack + i - matched;
}

int main( void ) {

    char *hay = "longlongagoinagalaxyfarfarawaygeorgelucasmadeababananana";

    char *needles[] = { "long", "far", "lucas", "yoda", "force", "banana", "nananana" };

    for( size_t i = 0; i < sizeof needles/sizeof needles[0]; i++ ) {
        printf( "%s:\n", needles[i] );
        size_t count = 0;
        for( char *p = hay; ( p = str_find( needles[i], p ) ) != NULL; p++ )
            printf( "\t#%d '%-.10s'\n", ++count, p );

        printf( "%d instances\n", count );
    }

    return 0;
}

输出显示“针”以及针后面的一些“上下文”字符。

long:
        #1 'longlongag'
        #2 'longagoina'
2 instances
far:
        #1 'farfaraway'
        #2 'farawaygeo'
2 instances
lucas:
        #1 'lucasmadea'
1 instances
yoda:
0 instances
force:
0 instances
banana:
        #1 'bananana'
1 instances
nananana:
0 instances

Answer 2

您可以重写此函数以不使用 strlen。首先，您使用结果来查看字符串的长度是否为 0，但您可以通过仅检查第一个字符是否为 0 来做到这一点。

稍后您可以使用长度来检查 for 循环的结束。您可以再次检查该点的字符串，看看它是否为 0。

这样你就不必使用字符串库了。

Answer 3

是否有可能/如何在不使用库的情况下编写此代码？

是的，这是可能的。

---

当前代码有问题/弱点：

int

vs

size_t

对于大字符串，长度可能会超过

int

。函数目标确实希望在某些情况下重新运行 -1，最好使用至少包含 1/2

size_t

范围的有符号整数，例如

long

或

long long

或最好：来自

ptrdiff_t

的

<stddef.h>

。

const

由于字符串未修改，因此使用

const char *

参数可以更广泛地使用。

功能可疑

如果不是

null 字符

，则

if (haystack[par_2 + par_1]) break;简单地中断循环。未完成匹配。

效率

OP 的代码似乎使用了

O(needle_length*haystack_length)

方法。

O(needle_length + haystack_length)

存在算法。

在真正的搜索开始之前，

int haystack_length = strlen(haystack);

并不需要遍历整个

haystack

。

考虑测试空字符。

// for(int par_2 = 0; par_2 < haystack_length; par_2++) 
for(int par_2 = 0; haystack[par_2]; par_2++) 

int needle_length = strlen(needle);

也不需要。当

needle[par_1] == 0

时停止比较

---

考虑

// int str_find( char* needle, char* haystack) 
ptrdiff_t str_find(const char* needle, const char* haystack) 

---

至少代码有好的参数名称

str_find(char* needle, char* haystack)

。