文档章节

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

北风其凉
 北风其凉
发布于 2014/06/04 15:30
字数 812
阅读 80
收藏 0
点赞 1
评论 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;
}

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 114
博文 493
码字总数 462457
作品 4
朝阳
程序员
大神有话说之c++,还在迷茫的朋友可以来看一下

C++ 是一种中级语言,它是由 Bjarne Stroustrup 于 1979 年在贝尔实验室开始设计开发的。C++ 进一步扩充和完善了 C 语言,是一种面向对象的程序设计语言。C++ 可运行于多种平台上,如 Window...

悟空_b201 ⋅ 05/30 ⋅ 0

c语言编程软件有哪些 Win7下用哪种C语言编译器

C语言是一门历史很长的编程语言,其编译器和开发工具也多种多样,其开发工具包括编译器,现举几个开发工具供大家选择,当然也要根据自己的操作系统来选择适合自己的开发工具 好多刚开始接触c...

mini92 ⋅ 04/20 ⋅ 0

C语言编程学习—宏定义的一些使用技巧

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/24 ⋅ 0

C语言编程能用来干嘛,为什么你觉得C语言学了之后没用?

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/10 ⋅ 0

考研复试系列——第十节 字符串问题

考研复试系列——第十节 字符串问题 前言 Sunday,DFS等等)。 例题一 完成这道题目了。 #include include using namespace std; const int state_zero = 0, //定义四个状态state_one = 1,s...

cassiepython ⋅ 2017/03/11 ⋅ 0

C语言编程入门基础学习:替换字符串中的空格的实现

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/30 ⋅ 0

jni在C/C++代码中调用java函数,java函数的参数是接口,有办法吗?

先上一段安卓下面搜索BLE的代码: 这里面的this是一个回调接口,当搜索到蓝牙设备时,会回调该接口。 在安卓上面用java没问题,但是现在需要在C++函数中实现这一段。 步骤描述: C++: 1 获取...

lvrenyang ⋅ 05/22 ⋅ 0

C语言/C++编程代码训练—昨天练习题进行讲解—真正的小项目

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/25 ⋅ 0

跪求大佬对java web项目与桌面应用数据交互方面给予指导!

最近在做一个java web项目,其中有个模块,需要在web项目中点击某个按钮的时候向一个桌面应用程序(另一个团队使用C/C++写的程序)发送一个指令。说到底就是javaweb项目中向C/C++项目发送一个...

Daisygeo ⋅ 04/23 ⋅ 0

什么是 C 和 C ++ 标准库?

简要介绍编写C/C ++应用程序的领域,标准库的作用以及它是如何在各种操作系统中实现的。 我已经接触C++一段时间了,一开始就让我感到疑惑的是其内部结构:我所使用的内核函数和类从何而来? ...

oschina ⋅ 04/10 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Python模块/包/库安装(6种方法)

Python模块/包/库安装(6种方法) 冰颖机器人 2016-11-29 21:33:26 一、方法1: 单文件模块 直接把文件拷贝到 $python_dir/Lib 二、方法2: 多文件模块,带setup.py 下载模块包(压缩文件zip...

cswangyx ⋅ 13分钟前 ⋅ 0

零基础学习大数据人工智能,学习路线篇!系统规划大数据之路?

大数据处理技术怎么学习呢?首先我们要学习Python语言和Linux操作系统,这两个是学习大数据的基础,学习的顺序不分前后。 Python:Python 的排名从去年开始就借助人工智能持续上升,现在它已经...

董黎明 ⋅ 21分钟前 ⋅ 0

openJdk和sun jdk的区别

使用过LINUX的人都应该知道,在大多数LINUX发行版本里,内置或者通过软件源安装JDK的话,都是安装的OpenJDK, 那么到底什么是OpenJDK,它与SUN JDK有什么关系和区别呢? 历史上的原因是,Ope...

jason_kiss ⋅ 31分钟前 ⋅ 0

梳理

Redux 是 JavaScript 状态容器,提供可预测化的状态管理。 它是JS的状态容器,是一种解决问题的方式,所以即可以用于 react 也可以用于 vue。 需要理解其思想及实现方式。 应用中所有的 stat...

分秒 ⋅ 43分钟前 ⋅ 0

Java 后台判断是否为ajax请求

/** * 是否是Ajax请求 * @param request * @return */public static boolean isAjax(ServletRequest request){return "XMLHttpRequest".equalsIgnoreCase(((HttpServletReques......

JavaSon712 ⋅ 今天 ⋅ 0

Redis 单线程 为何却需要事务处理并发问题

Redis是单线程处理,也就是命令会顺序执行。那么为什么会存在并发问题呢? 个人理解是,虽然redis是单线程,但是可以同时有多个客户端访问,每个客户端会有 一个线程。客户端访问之间存在竞争...

码代码的小司机 ⋅ 今天 ⋅ 0

到底会改名吗?微软GVFS 改名之争

微软去年透露了 Git Virtual File System(GVFS)项目,GVFS 是 Git 版本控制系统的一个开源插件,允许 Git 处理 TB 规模的代码库,比如 270 GB 的 Windows 代码库。该项目公布之初就引发了争...

linux-tao ⋅ 今天 ⋅ 0

笔试题之Java基础部分【简】【二】

1.静态变量和实例变量的区别 在语法定义上的区别:静态变量前要加static关键字,而实例变量前则不加。在程序运行时的区别:实例变量属于某个对象的属性,必须创建了实例对象,其中的实例变...

anlve ⋅ 今天 ⋅ 0

Lombok简单介绍及使用

官网 通过简单注解来精简代码达到消除冗长代码的目的 优点 提高编程效率 使代码更简洁 消除冗长代码 避免修改字段名字时忘记修改方法名 4.idea中安装lombnok pom.xml引入 <dependency> <grou...

to_ln ⋅ 今天 ⋅ 0

【转】JS浮点数运算Bug的解决办法

37.5*5.5=206.08 (JS算出来是这样的一个结果,我四舍五入取两位小数) 我先怀疑是四舍五入的问题,就直接用JS算了一个结果为:206.08499999999998 怎么会这样,两个只有一位小数的数字相乘,怎...

NickSoki ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部