BF算法 c#实现

　　串的模式匹配算法，主要对子串可进行固定位运算。常见的模式匹配算法包括BF算法和KMP算法，其中BF算法是最直观简单的，但效率较低。KMP算法通过之前匹配的结果进行合理的选择下一步指针指向的位置。

1. BF算法

　　假设存在2个字符串S和T，其中S为主串，T为模式串，字符串对应的下标分别用i和j表示，判断其是否匹配。S=“abababcabcacbab”，T=”abcac”。

　　BF模式匹配中将主串和子串的第一个元素进行对比，如果相等，i和j各向后移动一位，即i=i+1,j=j+1。如果不相同，则i向后移动一位，模式串T从第一个字符开始进行对比判断是否相同。

　　具体算法过程如下图所示：

BF算法的c#实现如下所示：

static void Main(string[] args)
        {
            Char[] s = {\'a\',\'b\',\'a\',\'b\',\'c\',\'a\',\'b\',\'c\',\'a\',\'c\',\'b\',\'a\',\'b\'};
            Char[] t = { \'a\', \'b\', \'c\', \'a\', \'c\' };
            int result=BruteForce(s,t);
            Console.WriteLine("子串在主串中中匹配的起始位置下标为：{0}", result);
            Console.Read();

        }
        /// <summary>
        /// 模式匹配算法——BF算法
        /// 时间复杂度为：最好的情况O(n+m);最坏的情况：O(n*m)
        /// </summary>
        /// <param name="s"></param>
        /// <param name="t"></param>
        /// <returns></returns>
        public static int BruteForce(Char[] s,Char[] t)
        {
            if (s.Length == 0 || t.Length == 0)
                Console.WriteLine("请重新输入字符串");
           int i=0;
           int j=0;
           int num = 0;
            if(i < s.Length)
            {
                while (j < t.Length)
                {
                    if (s[i] == t[j])
                    {
                        i++;
                        j++;
                    }
                    else
                    {
                        num++;
                        i = num;
                        j = 0;
                    }
                }
             }
            return i-t.Length;
        }

2. KMP算法

　　作者：海纳
　　链接：https://www.zhihu.com/question/21923021/answer/281346746
　　来源：知乎

　　KMP算法的核心，是一个被称为部分匹配表(Partial Match Table)的数组。对于字符串“abababca”，它的PMT如下表所示：

char	a	b	a	b	a	b	c	a
index	0	1	2	3	4	5	6	7
value	0	0	1	2	3	4	0	1

　　就像例子中所示的，如果待匹配的模式字符串有8个字符，那么PMT就会有8个值。

　　我先解释一下字符串的前缀和后缀。如果字符串A和B，存在A=BS，其中S是任意的非空字符串，那就称B为A的前缀。例如，”Harry”的前缀包括{”H”, ”Ha”, ”Har”, ”Harr”}，我们把所有前缀组成的集合，称为字符串的前缀集合。同样可以定义后缀A=SB，其中S是任意的非空字符串，那就称B为A的后缀，例如，”Potter”的后缀包括{”otter”, ”tter”, ”ter”, ”er”, ”r”}，然后把所有后缀组成的集合，称为字符串的后缀集合。要注意的是，字符串本身并不是自己的后缀。

　　有了这个定义，就可以说明PMT中的值的意义了。PMT中的值是字符串的前缀集合与后缀集合的交集中最长元素的长度。

　　以上述字符串为例说明计算其value值。

字符串	前缀	后缀	value
a	null	null	0
ab	a	b	0
aba	{a,ab}	{ba,a}	1
abab	{a,ab,aba}	{bab,ab,b}	2
ababa	{a,ab,aba,abab}	{baba,aba,ba,a}	3
ababab	{a,ab,aba,abab,ababa}	{babab,abab,bab,ab,b}	4
abababc	{a,ab,aba,abab,ababa,ababab}	{bababc,ababc,babc,abc,bc,c}	0
abababca	{a,ab,aba,abab,ababa,ababab,abababc}	{bababca,ababca,babca,abca,bca,ca,a}	1

　　解释清楚这个表之后，我们再来看如何使用这个表来加速字符串的查找及其原理。

　　如下图所示，字符串进行匹配时，如果在第J位不匹配，那么主串中S[i-j]~~S[i]位的元素与模式串中T[0]~~T[j-1]位相同。此时，下一步进行指针移动时，保持i指针不动，模式串T的指针后移至PMT[j-1]。

　　简言之，以图中的例子来说，在 i 处失配，那么主字符串和模式字符串的前边6位就是相同的。又因为模式字符串的前6位，它的前4位前缀和后4位后缀是相同的，所以我们推知主字符串i之前的4位和模式字符串开头的4位是相同的。就是图中的灰色部分。那这部分就不用再比较了。(j移动的位数即next值)

　　有了上面的思路，我们就可以使用PMT加速字符串的查找了。我们看到如果是在 j 位失配，那么影响 j 指针回溯的位置的其实是第 j −1 位的 PMT 值，所以为了编程的方便，我们不直接使用PMT数组，而是将PMT数组向后偏移一位。我们把新得到的这个数组称为next数组。下面给出根据next数组进行字符串匹配加速的字符串匹配程序。其中要注意的一个技巧是，在把PMT进行向右偏移时，第0位的值，我们将其设成了-1，这只是为了编程的方便，并没有其他的意义。在本节的例子中，next数组如下表所示。