检查 Char Array 是否包含特殊序列而不使用 C 中 Unix 上的字符串库

Question

假设我们有一个字符数组和一个序列。接下来我们要检查 char 数组是否包含特殊序列 WITHOUT <string.h> LIBRARY：如果是 -> return true；如果没有 -> return 错误。

bool contains(char *Array, char *Sequence) {
     // CONTAINS - Function
     for (int i = 0; i < sizeof(Array); i++) {
         for (int s = 0; s < sizeof(Sequence); s++) {
             if (Array[i] == Sequence[i]) {
            
                 // How to check if Sequence is contained ?  
             }
         }
     }
    return false;
}
// in Main Function
char *Arr = "ABCDEFG";
char *Seq = "AB";
bool contained = contains(Arr, Seq);
if (contained) {
    printf("Contained\n");
} else {
    printf("Not Contained\n"); 
}

任何想法、建议、网站...？

提前致谢，问候，来自 ∆

Answer 1

这不是最有效的算法，但我不想对您的代码进行太多更改。

size_t mystrlen(const char *str)
{
    const char *end = str;
    while(*end++);

    return end - str - 1;
}

bool contains(char *Array, char *Sequence) {
     // CONTAINS - Function
     bool result = false;
     size_t s, i;

     size_t arrayLen = mystrlen(Array);
     size_t sequenceLen = mystrlen(Sequence);

    if(sequenceLen <= arrayLen)
    {
        for (i = 0; i < arrayLen; i++) {
            for (s = 0; s < sequenceLen; s++) 
            {
                if (Array[i + s] != Sequence[s]) 
                {
                    break;
                }
            }
            if(s == sequenceLen) 
            {
                result = true;
                break;
            }

        }
    }
    return result;
}

int main()
{
    char *Arr = "ABCDEFG";
    char *Seq = "AB";
    bool contained = contains(Arr, Seq);
    if (contained) 
    {
        printf("Contained\n");
    } 
    else 
    {
        printf("Not Contained\n"); 
    }
}

Answer 2

最简单的方法是简单的搜索功能：

for (i = 0; i < lenS1; i++) {
    for (j = 0; j < lenS2; j++) {
        if (arr[i] != seq[j]) {
            break; // seq is not present in arr at position i!
        }
    }
    if (j == lenS2) {
        return true;
    }
 }

请注意，您不能使用 sizeof，因为您寻求的值在运行时未知。 Sizeof 将 return 指针大小，因此无论您使用什么字符串，几乎可以肯定总是四个或八个。您需要显式计算字符串长度，这在 C 中是通过知道字符串的最后一个字符为零来完成的：

lenS1 = 0;
while (string1[lenS1]) lenS1++;
lenS2 = 0;
while (string2[lenS2]) lenS2++;

一个明显而简单的改进是将 i 限制在 0 和 lenS1 - lenS2 之间，如果 lenS1 < lenS2，立即 return false。显然，如果您在到达 'L' 时还没有在“WELCOME”中找到“HELLO”，那么在剩下的四个字符 COME 中就不可能包含五个字符的 HELLO：

if (lenS1 < lenS2) {
    return false; // You will never find "PEACE" in "WAR".
}
lenS1minuslenS2 = lenS1 - lenS2;

for (i = 0; i < lenS1minuslenS2; i++)

进一步改进取决于您的用例。

在大量数组中寻找相同的序列，总是在同一个数组中寻找不同的序列，在大量不同的数组中寻找大量不同的序列 - 所有这些都需要不同的优化。

字符在数组和序列中的长度和分布也很重要，因为如果您知道在一个长字符串中只有（比方说）三个 E，并且您知道它们在哪里，您就需要搜索对于 HELLO，只有三个地方适合使用 HELLO。所以你不需要扫描整个“我们祝你圣诞快乐，我们祝你圣诞快乐，新年快乐”字符串。实际上你可能会注意到数组中没有 L 并且立即 return false.

一般用例的平衡选项（它确实有病理情况）可能由Boyer-Moore string matching algorithm提供（C源代码和解释在link).这有一个设置成本，所以如果你需要在 非常大的文本 中寻找不同的 短字符串 ，这不是一个好的选择（有并行搜索版本，适用于其中一些情况。

Answer 3

基本上这是strstr

const char* strstrn(const char* orig, const char* pat, int n)
{
    const char* it = orig;
    do
    {
        const char* tmp = it;
        const char* tmp2 = pat;
        if (*tmp == *tmp2) {
            while (*tmp == *tmp2 && *tmp != '[=10=]') {
                tmp++;
                tmp2++;
            }
            if (n-- == 0)
                return it;
        }
        tmp = it;
        tmp2 = pat;
    } while (*it++ != '[=10=]');
    return  NULL;
}

上述returns n 匹配字符串中的子串。

检查 Char Array 是否包含特殊序列而不使用 C 中 Unix 上的字符串库

Check if Char Array contains special sequence without using string library on Unix in C

c

unix

arrays

function

sequence