文档章节

几个用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;
}

© 著作权归作者所有

共有 人打赏支持
北风其凉

北风其凉

粉丝 114
博文 498
码字总数 463468
作品 4
朝阳
程序员
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
0
0
编程注释大家都会写吧,这种“挨踢”的注释玩过没?

注释大家都会写,主要用来帮助程序员理解代码的意思,下面列举了几个真实的注释,如果是当您接手这样的项目看到这样的注释时,会做如何反应呢?笔者这里表示已经哭笑不得了… 1.看下面的这段...

这个人很懒什么都没留下
07/23
0
0
大神有话说之c++,还在迷茫的朋友可以来看一下

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

悟空_b201
05/30
0
0
偷Microsoft师学MFC艺:且看C++如何支持反射

如果你问一个IT人士“C++如何实现类似Java的反射?”,结果会怎样呢?~!@#¥%……&,估计大部分人都会要稍微思考了一下,或者直接说“C++根本就不支持反射的呀!”。 是的,C++语言本身是不...

雅各宾
2015/04/17
0
0

没有更多内容

加载失败,请刷新页面

加载更多

你为什么在Redis里读到了本应过期的数据

一个事故的故事 晚上睡的正香突然被电话吵醒,对面是开发焦急的声音:我们的程序在访问redis的时候读到了本应过期的key导致整个业务逻辑出了问题,需要马上解决。 看到这里你可能会想:这是不...

IT--小哥
今天
2
0
祝大家节日快乐,阖家幸福! centos GnuTLS 漏洞

yum update -y gnutls 修复了GnuTLS 漏洞。更新到最新 gnutls.x86_64 0:2.12.23-22.el6 版本

yizhichao
昨天
5
0
Scrapy 1.5.0之选择器

构造选择器 Scrapy选择器是通过文本(Text)或 TextResponse 对象构造的 Selector 类的实例。 它根据输入类型自动选择最佳的解析规则(XML vs HTML): >>> from scrapy.selector import Sele...

Eappo_Geng
昨天
4
0
Windows下Git多账号配置,同一电脑多个ssh-key的管理

Windows下Git多账号配置,同一电脑多个ssh-key的管理   这一篇文章是对上一篇文章《Git-TortoiseGit完整配置流程》的拓展,所以需要对上一篇文章有所了解,当然直接往下看也可以,其中也有...

morpheusWB
昨天
5
0
中秋快乐!!!

HiBlock
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部