求一份BM算法的C#代码实现

Question

本帖最后由 Greyson_Xu 于 2011-10-17 14:29:42 编辑

Answer 1

一般比较少人专门写这个，网上很多c的BM算法，你改一下就行，不懂转的代码再在这问。
http://hi.baidu.com/sicceer/blog/item/2c7d173ffe238ce754e723d1.html

Answer 2

http://www.iteye.com/topic/353137可不可以按照这份C语言的代码帮我转下试试啊，我觉得这份写的比较清晰

Answer 3

我自己转了下，发现有点bug，注释在代码里面，各位看一下using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            loop:
            Console.WriteLine("输入文本字符串：");
            string a=Console.ReadLine();
            int s=a.Length;
            Console.WriteLine("输入模板：");
                string b=Console.ReadLine();
                int plen = b.Length;
               int[]skip= MakeSkip(b, plen);
               int[] shift = MakeShift(b, plen);
               int i = BMSearch(a, s, b, plen, skip, shift);
               Console.WriteLine(i);
               goto loop;
        }
        static int[] MakeSkip(string ptrn, int plen)
        {
            int a=0;
            int[] skip = new int[256];
            for (int i = 0; i < 256; i++)
            {
                skip[i] = plen;
            }
            while(plen!=0)
            {
                skip[ptrn[a++]] = plen--;
            }
            return skip;
        }        static int[] MakeShift(string ptrn, int plen)
        {
            int[] shift = new int[plen];
            int pptr=plen-1;
            int sptr=plen - 1;
            char c;
            c = ptrn[plen - 1];
            shift[sptr]=1;
            //pptr--;          
            while (sptr-- != 0)
            {
               int p1=plen-2,p2,p3; 
            
                 do{
                     while(p1>=0&&ptrn[p1--]!=c);                     p2=plen-2;
                     p3=p1;                     while(p3>0&&ptrn[p3--]==ptrn[p2--]&&p2>=pptr);                    }while(p3>=0&&p2>=pptr);                 shift[sptr]=plen-sptr+p2-p3;
                 pptr--;
             }
            return shift;
        }
        //bug:当匹配模板只有一个字符，并且与文本的第一个字符不匹配时出现bug；待修改。
        static int BMSearch(string buf, int blen, string ptrn, int plen, int[] skip, int[] shift)
        {
            int b_idx = plen;
            if (plen == 0)
                return 1;
            while (b_idx <= blen)
            {
                int p_idx = plen, skip_stride, shift_stride;
                while (buf[--b_idx] == ptrn[--p_idx])
                {
                    if (b_idx < 0)
                        return 0;
                    if (p_idx == 0)
                    {
                        return 1;
                    }
                }
                skip_stride = skip[buf[b_idx]];
                shift_stride = shift[p_idx];
                b_idx += (skip_stride > shift_stride) ? skip_stride : shift_stride;
            }
            return 0;
        }    }
}

Answer 4

顶一下,bug在哪呢?
C转C#要注意一些变量的长度不一样的问题,编码格式等等

Answer 5

//bug:当匹配模板只有一个字符，并且与文本的第一个字符不匹配时出现bug；待修改。

Answer 6

居然跑到我空间里去留言，你怎么找到我的？下面的代码暂时只支持ASCII字符        static int BmSerach(byte[] source, byte[] template) {
            // Prepare BmBc
            int[] bmBc = new int[256];
            for(int i = 0; i < bmBc.Length; ++i)
                bmBc[i] = template.Length;
            for(int i = 0; i < template.Length - 1; ++i)
                bmBc[template[i]] = template.Length - 1 - i;            // Prepare Suffix
            int[] suff = new int[template.Length];
            suff[suff.Length - 1] = template.Length;
            for(int i = template.Length - 2; i >= 0; --i) {
                int q = i;
                while(q >= 0 && template[q] == template[template.Length - 1 - (i - q)])
                    --q;
                suff[i] = i - q;
            }            // Prepare BmGs
            int[] bmGs = new int[template.Length];
            for(int i = 0; i < bmGs.Length - 1; i++)
                bmGs[i] = template.Length;
            int j = 0;
            for(int i = template.Length - 1; i >= 0; --i)
                if(suff[i] == i + 1)
                    for(; j < template.Length - 1 - i; ++j)
                        if(bmGs[j] == template.Length)
                            bmGs[j] = template.Length - 1 - i;
            for(int i = 0; i <= template.Length - 2; ++i)
                bmGs[template.Length - 1 - suff[i]] = template.Length - 1 - i;
            bmGs.ToList().ForEach(x => Console.Write(x.ToString() + ' '));
            Trace.WriteLine("");            // Search
            j = 0;
            while(j < source.Length - template.Length) {
                int i = template.Length - 1;
                for(; i >= 0 && template[i] == source[j + i]; i--) ;
                if(i < 0)
                    return j;
                else {
                    int step = Math.Max(bmBc[source[j + i]], bmGs[i]);
                    j += step;
                    Console.WriteLine("STEP:" + j);
                }
            }
            return -1;
        }        static void Main(string[] args) {
        loop:
            Console.WriteLine("输入文本字符串：");
            string a = Console.ReadLine();
            Console.WriteLine("输入模板：");
            string b = Console.ReadLine();
            int i = BmSerach(Encoding.ASCII.GetBytes(a), Encoding.ASCII.GetBytes(b));
            Console.WriteLine(i);
            goto loop;
        }

Answer 7

呵呵，你回的有点晚了啊，我刚刚结晚贴…………srry！一般来留言的都有分，人少么就多拿，如果都不是好的答案，又分配不均匀么，则前楼多拿。我性子比较急啊……还以为你不看留言的。。还有什么补救措施不