c - 下面的代码如何运行？

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 9 年前。

Improve this question

以下代码返回字符串 s1 中出现字符串 s2 中的任何字符的第一个位置。其最坏时间复杂度为O(m+n)。怎么办？

#include<stdio.h> 

int any(char *s1, char *s2) 
{

    char array[256]; 

    int  i;
    if (s1 == NULL) {
        if (s2 == NULL) {
            return(0);
        } else {
            return(-1);
        }
    }

    for(i = 0; i < 256; i++) {
        array[i] = 0;
    }

    while(*s2 != '\0') {
        array[*s2] = 1;
        s2++;
    }

    i = 0;
    while(s1[i] != '\0') {
        if (array[s1[i]] == 1) {
            return(i);
        }
        i++;
    }
    return(-1);
}

Answer 1

它分两步完成此操作。

1. 它初始化一个大小为 256 的数组(表示其输入字符串的每个有效字符)，并且对于 s2 (n) 中的每个字母，将数组中的字符标记为1 表示该字符存在。

2. 它迭代 s1 中的字符(0 到 m)，检查数组中的每个字符位置，看看它是否设置为“present”(1)，这将表明它在第二个字符串中。如果是，则返回该字符在 s1 中的索引。如果 s1 中的任何字符都不存在于 s2 中(在 m 处发现)，则返回 -1。

由于步骤 1 始终需要 n(s2 的长度)，而步骤 2 最多需要 m(s1 的长度)，所以最坏的情况是 O (m+n)，仅当没有匹配项或仅 s1 中的最后一个字符出现在 s2 中时才会发生。