几个用C++写的字符串搜索代码
几个用C++写的字符串搜索代码
北风其凉 发表于4年前
几个用C++写的字符串搜索代码
  • 发表于 4年前
  • 阅读 77
  • 收藏 0
  • 点赞 1
  • 评论 0

标题:腾讯云 新注册用户域名抢购1元起>>>   

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

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;
}

共有 人打赏支持
北风其凉
粉丝 111
博文 486
码字总数 458677
作品 4
×
北风其凉
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: