c - 以下代码如何运行？

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 中的索引。如果 s2 中不存在 s1 中的任何字符（在m处发现），则返回 -1。

由于步骤 1 将始终占用n（s2 的长度），而步骤 2 将占用m（s1 的长度），因此最坏的情况是 O(m+n)，仅当没有匹配项时才会发生，或者只有 s1 中的最后一个字符出现在 s2 中。