前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >KMP algorithm challenge string.Contains

KMP algorithm challenge string.Contains

作者头像
ShenduCC
发布2019-04-17 17:28:13
3770
发布2019-04-17 17:28:13
举报
文章被收录于专栏:算法修养算法修养

KMP:

代码语言:javascript
复制
 public int KMP (ReadOnlySpan<char> content, ReadOnlySpan<char> span) {
            _next = new int[span.Length];
            GetNext (span);
            int i = 0;
            int j = 0;
            while (i < content.Length && j < span.Length) {
                if (j == 0 || content[i] == span[j]) {
                     if(content[i]==span[j])
                        j++;
                    i++;
                   
                } else
                    j = _next[j];
            }
            if (j >= span.Length)
                return i - span.Length;
            else
                return -1;

        }

        private void GetNext (ReadOnlySpan<char> content) {
            _next[0] = 0;
            for (int i = 1; i < _next.Length; i++) {
                if (_next[i - 1] != 0) {
                    if (content[i] == content[_next[i - 1]])
                        _next[i] = _next[i - 1] + 1;
                } else {
                    if (content[0] == content[i])
                        _next[i] = 1;
                    else
                        _next[i] = 0;
                }
            }
        }

string.Contains and KMP benchmarks:

代码语言:javascript
复制
  [Benchmark]
        public void TestStringContain()
        {
            string s = "abcasdfasfdkjefasdfasdaaadfdfasdfasdfasdfjjsdjfjsglskdfjskdjfaskjdflkasjgksajdfksjdf";
            bool x = s.Contains("asdfasd",StringComparison.Ordinal);
        }

         [Benchmark]
        public void TestKMP()
        {
            int x = containKeyWords.KMP("abcasdfasfdkjefasdfasdaaadfdfasdfasdfasdfjjsdjfjsglskdfjskdjfaskjdflkasjgksajdfksjdf", "asdfasd");
        }

result:

Complete defeat!

本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2019-04-04 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档