导航：首页 > 互联网科技 >

KMP 算法的应用（二十七）

发表于：2024-11-24 作者：热门IT资讯网编辑

编辑最后更新 2024年11月24日，我们在上节博客中讲到了 KMP 算法的具体实现，那么我们本节就来看看 KMP 算法的应用。问题：如何在目标字符串中查找是否存在指定的子串？我们来看看字符串类中的新功能，如下图所示1、子串查找（KMP

我们在上节博客中讲到了 KMP 算法的具体实现，那么我们本节就来看看 KMP 算法的应用。问题：如何在目标字符串中查找是否存在指定的子串？

我们来看看字符串类中的新功能，如下图所示

1、子串查找（KMP 算法的直接应用）

int indexOf(const char* s) const;

int indexOf(const String& s) const;

我们来看看具体源码的实现，如下

int String::indexOf(const char* s) const{    return kmp(m_str, s ? s : "");}int String::indexOf(const String& s) const{    return kmp(m_str, s.m_str);}

直接利用我们上节博客实现的 kmp 函数就能实现 indexOf 函数，我们来看看效果

#include #include #include "DTString.h"using namespace std;using namespace DTLib;int main(){    String s = "ababax";    cout << s.indexOf("bax") << endl;    return 0;}

编译运行结果如下

我们看到返回的位置为下标为 3 处，也就是 s[3] 处。

2、在字符串中将指定的子串删除

String& remove(int i, int len);

String& remove(const char* s);

String& remove(const String& s);

根据 KMP 在目标字符串中查找子串的位置，再通过子串位置和子串长度进行删除。具体源码实现如下

String& String::remove(int i, int len){    if( (0 <= i) && (i < m_length) )    {        int n = i;        int m = i + len;        while( (n < m) && (m < m_length) )        {            m_str[n++] = m_str[m++];        }        m_str[n] = '\0';        m_length = n;    }    return *this;}String& String::remove(const char* s){    return remove(indexOf(s), s ? strlen(s) : 0);}String& String::remove(const String& s){    return remove(indexOf(s), s.length());}

我们来写个测试代码进行测试，如下

#include #include #include "DTString.h"using namespace std;using namespace DTLib;int main(){    String s = "ababax";    cout << s.remove("bab").str() << endl;    return 0;}

我们来看看结果是不是 aax，如下

3、字符串的减法操作定义（operator -）

使用 remove 实现字符串间的减法操作，必须得保证字符串自身不被修改，返回产生的新串。最后效果如下

String operator - (const String& s) const;

String operator - (const char* s) const;

String& operator -= (const String& s);

String& operator -= (const char* s);

利用原有的 + 操作符进行改装即可，源码实现如下

String String::operator - (const String& s) const{    return String(*this).remove(s);}String String::operator - (const char* s) const{    return String(*this).remove(s);}String& String::operator -= (const String& s){    return remove(s);}String& String::operator -= (const char* s){    return remove(s);}

我们来测试下，测试代码如下

#include #include #include "DTString.h"using namespace std;using namespace DTLib;int main(){    String s = "ababax";    String s1 = s - "bax";    cout << s.str() << endl;    cout << s1.str() << endl;    s -= s;    cout << "[" << s.str() << "]" << endl;    return 0;}

我们来看看运行结果，s1 = "aba", 最后的 s 应该为空，我们来看看结果

我们看到结果正如我们所分析的那样。

4、字符串中的子串替换

String& replace(const char* t, const char* s);

String& replace(const String& t, const char* s);

String& replace(const char* t, const String& s);

String& replace(const String& t, const String& s);

我们来看看具体源码的实现

String& String::replace(const char* t, const char* s){    int index = indexOf(t);    if( index > 0 )    {        remove(t);        insert(index, s);    }    return *this;}String& String::replace(const String& t, const char* s){    return replace(t.m_str, s);}String& String::replace(const char* t, const String& s){    return replace(t, s.m_str);}String& String::replace(const String& t, const String& s){    return replace(t.m_str, s.m_str);}

我们来写个测试代码进行测试，代码如下

#include #include #include "DTString.h"using namespace std;using namespace DTLib;int main(){    String s = "ababax";    s.replace("baba", "xyz");    cout << s.str() << endl;    return 0;}

我们来看看最后的结果是不是 axyzx，运行结果如下

5、从字符串中创建子串

String sub(int i, int len) const;

以 i 为起点提取长度为 len 的子串，子串提取保证不会改变字符串本身的状态。如下

具体源码实现如下

String String::sub(int i, int len) const{    String ret;    if( (0 <= i) && (i < m_length) )    {        if( len < 0 ) len = 0;        if( len > m_length ) len = m_length - i;        char* str = static_cast(malloc(len + 1));        strncpy(str, m_str + i, len);        str[len] = '\0';        ret = str;    }    else    {        THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid ...");    }    return ret;}

我们来写个测试代码进行测试，测试代码如下

#include #include #include "DTString.h"using namespace std;using namespace DTLib;int main(){    String s = "ababax";    String s1 = s.sub(3, 10);    String s2 = s.sub(2, 3);    cout << s.str() << endl;    cout << s1.str() << endl;    cout << s2.str() << endl;    return 0;}

最后的结果应该是 s = "ababax" ; s1 = "bax" ; s3 = "aba" ; 运行结果如下

现在我们的字符串类已经实现的有点规模了。通过今天对字符串类的学习，总结如下：1、字符串类是工程开发中必不可少的组件；2、字符串中应该包含常用的字符串操作函数，a> 增：insert， operator + ， ...； b> 删：remove，operator -，...； c> 查：indexOf，...； d> 改：replace，... 。

很赞哦！

KMP 算法的应用（二十七）

相关文章