刘系-20180819.md

算法

这是第一周提交，只写了算法部分，往后继续完善内容，争取把四个部分都写到。

KMP 匹配算法

这是一个高效的字符串匹配算法，字符串匹配要做的事情是在一个长字符串中找到一个子字符串，如果找到了就返回这个子字符串在长字符串中哪个位置起始，如果找不到就返回一个其他标志。下面分析算法是如何一步一步演变来的。为了方便说明，将长字符串叫为S，子字符串叫为T。

brute-force

这个名字叫野蛮的力量，其实说的是在解决字符串匹配时最容易想到的解决方案，对S中每个字符挨个与T中字符进行匹配。这个不多说，直接写代码。

// brure-force
int BF_Index(char *s, char *t, int pos)
{
    int m, n, i, j;
    m = strlen(s);
    n = strlen(t);
    i = pos;
    while(i <= (m-n))
    {
        for(j = 0; j < n; j++)
        {
            if(s[i + j] == t[j])
            {
                if(j == (n - 1))
                {
                    return i + 1;
                }
                continue;
            } 
            else 
            {
                i++;
                break;
            }
        }      
    }
    return -1;
}

KMP

BF算法能够解决字符串匹配的问题，但是还有可以改进的地方。比如在S=‘abcabcdefg123’中匹配T='abcd'，第一次匹配成功的‘abc’部分由于第四个字符‘d’不匹配而需要从‘bcabcdefg123’重新匹配。而事实上第一个‘abc’已经匹配过了，不需要再重新匹配，直接从第二个‘abc’处匹配即可。这就是KMP算法的核心思想，利用部分匹配的信息，减少冗余的匹配过程，从而提高效率。 算法有几个关键点：

• S字符串的索引不回溯
• 构建当字符不匹配时应该继续匹配T中何位置字符的索引（next）

虽然写出来就这么一点，但是这个算法实在是绕，经常想着想着就丢失焦点了，下面写几条我自己容易迷失的地方。

• 数组索引是从0开始还是从1开始
• next数组关注的不是T右移多少位，而是T下一个进行匹配的位置
• next计算时前缀取不取最后一个字符，后缀取不取第一个字符
• 匹配循环与BF一致，只是多了个next数组，根据不同情况更新S与T的索引即可

下面是代码

// kmp
void get_next(char *t, int *next)
{
    int n = strlen(t);
    int j = 2;
    next[0] = -1;
    if (n == 1)
    {
        return;
    }
    next[1] = 0;
    if (n == 2)
    {
        return;
    }
    while(j < n)
    {
        // 如果后缀最后一个字符与前缀最后一个字符相等，则将j位的next在next[j-1]基础上加1
        if (t[j - 1] == t[next[j - 1]]) 
        {
            next[j] = next[j - 1] + 1;
            j++;
        }
        // 如果上述条件不成立，判断后缀的最后一个字符是否与前缀的第一个字符相等，相等则j位置1
        else if (t[j - 1] == t[0]) 
        {
            next[j] = 1;
            j++;
        }
        // 如果上述两个条件均不成立，则前后缀没有公共部分，next置0
        else
        {
            next[j] = 0;
            j++;
        }
    }
    return;
}

int KMP_Index(char *s, char *t, int pos)
{
    int m, n, i, j, k;
    m = strlen(s);
    n = strlen(t);
    int next[n];
    get_next(t, next);
    i = pos;
    j = 0;
    while(i < (m - n))
    {
        if (s[i] == t[j])
        {
            if(j == (n - 1))
            {
                return i + 2 - n;
            }
            i++;
            j++;
            continue;
        }
        // 如果字符不匹配，根据当前位置对应的next值进行处理
        else
        {
            if (next[j] == -1)
            {
                i++;
            }
            else
            {
                j = next[j];
            }
        }
    }
    return -1;
}

int main(void)
{
    char a[100];
    char b[100];
    gets(a);
    gets(b);
    printf("%i", KMP_Index(a, b, 0));
    return 0;
}