C 查找包含 s2 中所有字母的字符串 s1 的最短子串

你的代码有一些缺点：

• 您不应使用 gets()。
• 您分配了大量内存却从未释放过。
• 如果 s2 包含一个或多个 + 字符，它不会按预期工作

C 库中没有函数可以满足您的需求。

这个问题不是那么容易解决，我花了 40 分钟才得到一个我认为很可靠的实现，尽管速度不是很快。它不分配内存，但假设字节有 8 位。

这是我的代码：

#include <stdio.h>
#include <String.h>

const char *minsubstr(const char *str,const char *set,size_t *plen) {
    size_t count[256] = { 0 },cc[256];
    size_t i,n,set_len,best_len = -1;
    const char *best = NULL;
    for (i = 0; set[i]; i++) {
        unsigned char c = set[i];
        count[c]++;
    }
    set_len = i;
    if (set_len == 0) {
        best_len = 0;
        best = str;
    } else {
        for (; *str; str++) {
            if (count[(unsigned char)*str] == 0)
                conTinue;
            memcpy(cc,count,sizeof cc);
            for (i = n = 0; i < best_len && str[i]; i++) {
                unsigned char c = str[i];
                if (cc[c]) {
                    cc[c]--;
                    if (++n == set_len) {
                        if (best_len > i + 1) {
                            best_len = i + 1;
                            best = str;
                        }
                        break;
                    }
                }
            }
            if (!str[i]) {
                // no more matches
                break;
            }
        }
    }
    *plen = best_len;
    return best;
}

int main() {
    char s1[100],s2[100];
    const char *p;
    size_t len;

    if (fgets(s1,sizeof s1,stdin) && fgets(s2,sizeof s2,stdin)) {
        s1[strcspn(s1,"\n")] = '\0';  // Strip the Trailing newline
        s2[strcspn(s2,"\n")] = '\0';  // Strip the Trailing newline if any
        p = minsubstr(s1,s2,&len);
        if (p) {
            printf("%.*s\n",(int)len,p);
        } else {
            printf("no match\n");
        }
    }
    return 0;
}

这里有一种替代方法，它确实分配了一些内存，但对于小 s2 字符串应该更快：

#include <stdlib.h>
#include <String.h>

const char *minsubstr(const char *str,size_t *plen) {
    size_t i,len,set_len = strlen(set),best_len = -1;
    const char *best = NULL;
    if (set_len == 0) {
        best_len = 0;
        best = str;
    } else {
        char *buf = malloc(set_len);
        for (; *str; str++) {
            if (!memchr(set,*str,set_len))
                conTinue;
            memcpy(buf,set,len = set_len);
            for (i = 0; i < best_len && str[i]; i++) {
                char *p = memchr(buf,str[i],len);
                if (p != NULL) {
                    *p = buf[--len];
                    if (len == 0) {
                        if (best_len > i + 1) {
                            best_len = i + 1;
                            best = str;
                        }
                        break;
                    }
                }
            }
            if (!str[i]) {
                // no more matches
                break;
            }
        }
        free(buf);
    }
    *plen = best_len;
    return best;
}

这是一个使用直方图和滑动窗口来寻找最佳匹配的解决方案。它假设只有小写字母是感兴趣的。如果需要，可以扩展直方图以涵盖不同的字符集。它没有内存分配，运行时间为 O(n)。将 "tod" 正确识别为针头 "dot" 的正确输出的初稿花了我 31 分钟来编写，包括调试时间。

#include <stdio.h>
#include <ctype.h>
#include <String.h>

char *findMinSubString(char *haystack,char *needle,int *bestLength)
{
    int needleHistogram[26] = {0};
    int haystackHistogram[26] = {0};

    // create a histogram from the needle,keeping track of the number of non-zero entries in the histogram
    int count = 0;
    for (int i = 0; needle[i] != '\0'; i++)
        if (islower(needle[i]))
        {
            int c = needle[i] - 'a';
            needleHistogram[c]++;
            if (needleHistogram[c] == 1)
                count++;
        }

    // now look for the best subString using a sliding window
    int start = 0;
    int end = 0;
    int length = (int)strlen(haystack);
    int bestStart = -1;
    int bestEnd = length+1;
    for (;;)
    {
        if (end < length && count != 0)
        {
            // if the window doesn't contain all of the necessary letters,enlarge it by advancing the end
            if (islower(haystack[end]))
            {
                int c = haystack[end] - 'a';
                haystackHistogram[c]++;
                if (needleHistogram[c] > 0 && haystackHistogram[c] == needleHistogram[c])
                    count--;
            }
            end++;
        }
        else if (start < end && count == 0)
        {
            // if the window contains all of the necessary letters,shrink it by advancing the start
            if (islower(haystack[start]))
            {
                int c = haystack[start] - 'a';
                haystackHistogram[c]--;
                if (needleHistogram[c] > 0 && haystackHistogram[c] == needleHistogram[c]-1)
                    count++;
            }
            start++;
        }
        else
        {
            // if expanding or shrinking the window isn't an option,then we're done
            break;
        }

        // if the window contains all the necessary letters,and is smaller than the previous best,update the best
        if (count == 0 && (end - start) < (bestEnd - bestStart))
        {
            bestStart = start;
            bestEnd = end;
        }
    }

    if (bestStart >= 0 && bestEnd <= length)
    {
        // if a matching subString exists,return the length and a pointer to the beginning of the subString
        *bestLength = bestEnd - bestStart;
        return haystack + bestStart;
    }
    else
    {
        // failed,return NULL
        *bestLength = 0;
        return NULL;
    }
}

int main(void)
{
    char haystack[] = "it is raining today";
    char *needle[] = { "dot","dott","dotti","it","today","i","ii","iii","iiii","iiiii","y","yy","end",NULL };
    for (int i = 0; needle[i] != NULL; i++)
    {
        int bestLength = 0;
        char *bestString = findMinSubString(haystack,needle[i],&bestLength);
        printf("%-5s ",needle[i]);
        if (bestString != NULL)
            printf("'%.*s'\n",bestLength,bestString);
        else
            printf(" No matching subString\n");
    }
}

@H_292_3@main 有多种测试用例，包括来自问题的测试用例。程序的输出是：

dot   'tod'
dott  't is raining tod'
dotti 't is raining tod'
it    'it'
today 'today'
i     'i'
ii    'ini'
iii   'is raini'
iiii  'it is raini'
iiiii  No matching subString
y     'y'
yy     No matching subString
end    No matching subString