趋势科技2011校园招聘两道编程题

1. 最长不重复子串
#include
#include
#include

#define DIFF_CHAR_NUM    256

/* 在字符串中查找最长不重复子串，返回最长不重复子串的下标和长度 */
size_t substring(char *src)
{
    assert(NULL != src);

    size_t ret;
    size_t maxLen = 0;
    size_t curLen = 0;
    size_t i = 0;
    size_t srcLen = strlen(src);
    char exist[DIFF_CHAR_NUM] = {0};

    while (i < srcLen)
    {
        if (exist[src[i]] == 0)
        {
            // 目前还没有重复的字符出现
            exist[src[i]] = i + 1;
            ++curLen;
            ++i;
            ret = i;
        }
        else
        {
            // 出现第一个重复的字符
            if (curLen > maxLen && curLen <= DIFF_CHAR_NUM)
            {
                maxLen = curLen;
            }
            else if (curLen > DIFF_CHAR_NUM)
            {
                maxLen = DIFF_CHAR_NUM;
                break;
            }
            ret = i;

            i = exist[src[i]];
            curLen = 0;
            memset(exist, 0, DIFF_CHAR_NUM * sizeof(char));
        }
    }

    // 总共256个不同的字符，若curLen > DIFF_CHAR_NUM时，此时一定会出现重复字符
    // 即最大不重复的子串长度为256
    if (curLen > maxLen && curLen <= DIFF_CHAR_NUM)
    {
        maxLen = curLen;
    }
    else if (curLen > DIFF_CHAR_NUM)
    {
        maxLen = DIFF_CHAR_NUM;
    }

    printf("max no-repeat substring length: %d\n", maxLen);

    char *buf = new char[maxLen + 1];
    buf[maxLen] = '\0';
    printf("max no-repeat substring: %s\n", strncpy(buf, &src[ret-maxLen], maxLen));
    delete[] buf;

    // 下标
    return (ret - maxLen);
}

int main(int argc, char **argv)
{
    char src[512];
    printf("Enter a string to find max non-repeat sub-string: ");
    scanf("%s", src);

    printf("Index of max non-duplicated substring: %d\n", substring(src));

    return 0;
}

测试结果：
Enter a string to find max non-repeat substring: abcdefaghijklabv
max non-repeat substring length: 12
max non-repeat substring: bcdefaghijkl
Index of max non-duplicated substring: 1

Enter a string to find max non-repeat substring: abcdefghijklmnopq
max non-repeat substring length: 17
max non-repeat substring: abcdefghijklmnopq
Index of max non-duplicated substring: 0


2. 假设一个数据量很大的文件[百万级以上]，文件每行记录一个用户名，用户身份信息，用户住址信息等，要求写出函数建立一个索引文件，给定某个用户名字，怎样快速找到用户的其他信息。写出函数void BuildIndexFile(const char* datafile); char* findSomeone(char* name);
欢迎有很好想法的同学们留言！