KMP算法

問題描述：給定字元串A和其子串B， 在A中查找B，傳回其下标

已給出BF解法和KMP解法

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

/* 簡單BF算法 */
int BF(const char *str, const char *substr)
{
    assert(str && substr);
    int lenStr = strlen(str);
    int lenSubstr = strlen(substr);
    if(lenStr < lenSubstr)
        return -;

    for(int i = ; i != lenStr-lenSubstr+; ++i)
    {
        int j;
        for(j = ; j != lenSubstr; ++j)
            if(str[i+j] != substr[j])
                break;
        if(j == lenSubstr)
            return i;
    }
    return -;
}

/* 擷取指針數組previous */
void getPrevious(const char *pattern, int lenPattern, int *previous)
{
    int curPos = ;
    previous[curPos] = -;
    int flagPos = -;
    while(curPos < lenPattern-)
    {
        if(- == flagPos || pattern[curPos] == pattern[flagPos])
        {
            ++curPos;
            ++flagPos;
            previous[curPos] = flagPos;
        }
        else
            flagPos = previous[flagPos];
    }
}

/* 改進的getPrevious */
void getPreviousBetter(const char *pattern, int lenPattern, int *previous)
{
    int curPos = ;
    previous[curPos] = -;
    int flagPos = -;
    while(curPos < lenPattern-)
    {
        if(- == flagPos || pattern[curPos] == pattern[flagPos])
        {
            ++curPos;
            ++flagPos;
            if(pattern[curPos] != pattern[flagPos])
                previous[curPos] = flagPos;
            else
                previous[curPos] = previous[flagPos];
        }
        else
            flagPos = previous[flagPos];
    }
}

/* KMP */
int KMP(const char *str, int lenStr, const char *pattern, int lenPattern, \
        const int *previous, int pos)
{
    int strPos = pos;
    int patternPos = ;
    while(strPos != lenStr && patternPos != lenPattern)
    {
        if(- == patternPos || str[strPos] == pattern[patternPos])
        {
            ++strPos;
            ++patternPos;
        }
        else
            patternPos = previous[patternPos];
    }
    if(patternPos == lenPattern)
        return strPos-lenPattern;
    else
        return -;
}

/* 問題描述：給定字元串A和其子串B， 在A中查找B，傳回其下标 */
int main(void)
{
    const char *str = "How are you";
    const char *substr = "are";
    printf("%d\n", BF(str, substr));

    const char *str2 = "001012012301234";
    const char *substr2 = "0120123";
    int previous[];
    getPrevious(substr2, strlen(substr2), previous);
//  getPreviousBetter(substr2, strlen(substr2), previous);
    printf("%d\n", KMP(str2, strlen(str2), substr2, strlen(substr2), previous, ));

    return ;
}