文档章节

几个用C++写的字符串搜索代码

北风其凉
 北风其凉
发布于 2014/06/04 15:30
字数 812
阅读 80
收藏 0

1.关于本文

本文中所有的代码都为实现一个目标,即:

写一个函数:从字符串s中找到字符串a第一次出现的位置,不存在则返回-1

2.方法1:朴素的字符串搜索算法

用一个循环来找出所有有效位移

#include<iostream>
#include<string>

using namespace std;

//函数:找出字符串s中第一次出现字符串a的位置(朴素算法)
int IndexOf_01(string s,string a)
{
    bool isMatch;
    for(int i = 0; i <= s.length() - a.length(); i++)
    {
        isMatch = true;
        for(int j = 0; j < a.length(); j++)
        {
            if(s[i + j] != a[j])
            {
                isMatch = false;
                break;
            }
        }

        if(isMatch)
        {
            return i;
        }
    }

    return -1;
}

int main()
{
    string s = "the quick brown fox jumped over the lazy dogs";

    cout << s << endl;
    cout << "index of \"the\": " << IndexOf_01(s, "the") << endl;
    cout << "index of \"quick\": " << IndexOf_01(s, "quick") << endl;
    cout << "index of \"dogs\": " << IndexOf_01(s, "dogs") << endl;
    cout << "index of \"cats\": " << IndexOf_01(s, "cats") << endl;

    return 0;
}

 

3.方法2

本方法受到了 Rabin-Karp 启发,相当于对原算法做了如下修改

窗口长度:m=a.length(),第一次匹配规则:t=t[0]+t[1]+...+t[t.length()-1],模p=max

对于字符串s的每一个长度为m的子串,如果该子串所有字符的ASCII码和与目标字符串相同,则逐个比对该子串与目标字符串是否相同,否则跳过。若子串与目标字符串相同,则认为匹配,否则继续向后搜索。

#include<iostream>
#include<string>

using namespace std;

//函数:找出字符串s中第一次出现字符串a的位置(受到Rabin-Karp算法启发)
int IndexOf_02(string s,string a)
{
    //s的长度应大于a的长度
    if(s.length() < a.length())
    {
        return -1;
    }

    //计算第一组数字和
    int target = 0, current = 0;
    for(int i = 0; i < a.length(); i++)
    {
        target += a[i];
        current += s[i];
    }

    //开始匹配
    bool isMatch;
    for(int i = 0; i <= s.length() - a.length(); )
    {
        //如果所有字符的数字和相同,则进一步比较
        if(current == target)
        {
            isMatch = true;
            for(int j = 0; j < a.length(); j++)
            {
                if(s[i + j] != a[j])
                {
                    isMatch = false;
                    break;
                }
            }

            if(isMatch)
            {
                return i;
            }
        }

        //计算下一组字符的数字和
        current -= s[i];
        current += s[i++ + a.length()];
    }

    return -1;
}

int main()
{
    string s = "the quick brown fox jumped over the lazy dogs";

    cout << s << endl;
    cout << "index of \"the\": " << IndexOf_02(s, "the") << endl;
    cout << "index of \"quick\": " << IndexOf_02(s, "quick") << endl;
    cout << "index of \"dogs\": " << IndexOf_02(s, "dogs") << endl;
    cout << "index of \"cats\": " << IndexOf_02(s, "cats") << endl;

    return 0;
}

4.Knuth-Morris-Pratt(KMP)算法

KMP算法,函数ComputePrefix用于计算辅助数组

#include<iostream>
#include<string>

using namespace std;

//计算前缀
int* ComputePrefix(string a)
{
    int *array = new int[a.length() + 1];

    int x = 0;
    array[0] = 0;
    for(int i = 1; i < a.length(); i++)
    {
        if(a[i] == a[x])
        {
            array[i] = array[i - 1] + 1;
            x++;
        }
        else
        {
            array[i] = 0;
            x = 0;
        }
    }

    return array;
}

//函数:找出字符串s中第一次出现字符串a的位置(KMP算法)
int IndexOf_KMP(string s, string a)
{
    //计算前缀
    int *perfix = new int[a.length()];
    perfix = ComputePrefix(a);

    //判断a在s中第一次出现的位置
    int x = 0, y = 0;
    while(x < s.length())
    {
        if(s[x + y] == a[y])
        {
            y++;
            if(y == a.length())
            {
                return x;
            }
        }
        else
        {
            if(y == 0)
            {
                x++;
            }
            else
            {
                x += (y - perfix[y - 1]);
            }
            y = 0;
        }
    }

    return -1;
}

int main()
{
    string tests = "ababaabababcabab";
    cout << tests << endl;

    string testa0 = "ababa";
    cout << testa0 << ": " << IndexOf_KMP(tests, testa0) << endl;

    string testa1 = "ababc";
    cout << testa1 << ": "  << IndexOf_KMP(tests, testa1) << endl;

    string testa2 = "cabab";
    cout << testa2 << ": " << IndexOf_KMP(tests, testa2) << endl;

    string testa3 = "aaaaa";
    cout << testa3 << ": " << IndexOf_KMP(tests, testa3) << endl;

    return 0;
}

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 115
博文 498
码字总数 463468
作品 4
朝阳
程序员
私信 提问
关于Nebula3工程的几个编译选项

研究一下人家是怎么通过编译选项来优化性能的 DEBUG: C++/Code Generation/Enable String Pooling: Yes (/GF) 该选项使编译器能够为执行过程中程序映像和内存中的相同字符串创建单个副本,从...

长平狐
2012/11/12
79
0
牛逼的C/C++程序员是如何练成的?

这个题目的噱头太大,要真的写起来, 足够写一本书了。 牛耳人分享一些经验,希望能让初学的小伙伴少走弯路。 每个人的情况不一样,所以下面的描述可能并不适合每一个看到这篇文章的人。 一、...

weixin_42743471
12/07
0
0
C++十种方法"Hello World"

初学编程,无论是VB,C/C++,Java,C#大多都是从Hellow World这个程序开 始的,也是最常见的入门方法。C/C++本身有很多特性和用发,这里就用十种方法 实现Hellow World这个程序. 1. 最经典的...

程序鸡
2012/12/07
0
3
C#调用C/C++封装的动态库(DLL)

本人初学C#,对C#里面的一些概念,比如委托之类的理解不是很深,现在需要用C#调用C++写的动态库,不知道怎么下手,还请大神帮忙。就是C#代码里面要怎么调用这些函数。 例如: dll里面的代码是...

惯犯
09/06
146
1
[WebKit内核] JavaScriptCore深度解析--基础篇(一)字节码生成及语法树的构建

看到HorkeyChen写的文章《[WebKit] JavaScriptCore解析--基础篇(三)从脚本代码到JIT编译的代码实现》,写的很好,深受启发。想补充一些Horkey没有写到的细节比如字节码是如何生成的等等,为此...

MichaelWH
2015/03/28
0
0

没有更多内容

加载失败,请刷新页面

加载更多

jquery通过id显示隐藏

var $div3 = $('#div3'); 显示 $div3.show(); 隐藏 $div3.hide();

yan_liu
57分钟前
1
0
《乱世佳人》读书笔记及相关感悟3900字

《乱世佳人》读书笔记及相关感悟3900字: 之前一直听「荔枝」,后来不知怎的转向了「喜马拉雅」,一听就是三年。上班的时候听房产,买房了以后听装修,兴之所至时听旅行,分手后听亲密关系,...

原创小博客
今天
1
0
大数据教程(9.6)map端join实现

上一篇文章讲了mapreduce配合实现join,本节博主将讲述在map端的join实现; 一、需求 实现两个“表”的join操作,其中一个表数据量小,一个表很大,这种场景在实际中非常常见,比如“订单日志...

em_aaron
今天
1
0
cookie与session详解

session与cookie是什么? session与cookie属于一种会话控制技术.常用在身份识别,登录验证,数据传输等.举个例子,就像我们去超市买东西结账的时候,我们要拿出我们的会员卡才会获取优惠.这时...

士兵7
今天
1
0
十万个为什么之为什么大家都说dubbo

Dubbo是什么? 使用背景 dubbo为什么这么流行, 为什么大家都这么喜欢用dubbo; 通过了解分布式开发了解到, 为适应访问量暴增,业务拆分后, 子应用部署在多台服务器上,而多台服务器通过可以通过d...

尾生
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部