复盘一道面试算法题

最近面试一个开发岗位，遇到一道算法题，现场我只给出了思路，没能在规定时间里写出代码也就没法现场验证，在这里复盘一下。

题目

只能回忆起部分内容，大致是，从一个给定的字符串中找出最长的重复的子串。

分析

假定输入字符串是 asdfddfbiibhddf234，长度为 18 个字符。

1. 子串：长度至少要为 1 个字符，最大 17 个字符。
2. 重复子串：当确定以一个子串，如以 asd 为目标寻找重复子串，那么寻找的范围必须是输入字符串中 a 字符之后的部分。
3. 需要遍历所有情况。

基于以上 3 条规则，我们可以得出如下思路：

1. 利用双重循环遍历所有可能出现的子串。
2. 使用 strstr 从输入字符串的子串首字母之后的部分中寻找是否有重复子串。
3. 更新最长子串记录。

代码

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

int substring(char *input, char **output)
{
    int i, j, n;
    int in_len = strlen(input);
    int max = 0;

    char *tmp;
    tmp = malloc(in_len);

    // 双重循环负责遍历所有子串
    // j 从 i+1 开始保证子串最短为 1 个字符
    // j < in_len 保证子串最大为 in_len-1 个字符
    for (i = 0; i < in_len; i++)
    {
        for (j = i + 1; j < in_len; j++)
        {
            // 子串长度
            n = j - i;
            // 取子串
            strncpy(tmp, input + i, n);
            tmp[n] = '\0';
            // 从子串首字符之后的剩余部分找重复子串
            if (strstr(input + i + 1, tmp))
            {
                if (n > max)
                {
                    *output = input + i;
                    max = n;
                }
            }
        }
    }

    free(tmp);

    return max;
}

int main(int argc, char *argv[])
{
    char *out;
    int len;
    int i;

    printf(" input: \"%s\"\n", argv[1]);

    len = substring(argv[1], &out);

    printf("output: \"");
    for (i = 0; i < len; i++)
        printf("%c", out[i]);
    printf("\"\n");

    return 0;
}

测试结果

测试字符串：asdfddfbiibhddf234
结果输出：

 input: "asdfddfbiibhddf234"
output: "ddf"

测试字符串：aaa
结果输出：

 input: "aaa"
output: "aa"

测试字符串：bbbb
结果输出：

 input: "bbbb"
output: "bbb"

测试字符串：c
结果输出：

 input: "c"
output: ""