KMP 算法的应用(二十七)

        我们在上节博客中讲到了 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 <iostream>
#include <cstring>
#include "DTString.h"

using namespace std;
using namespace DTLib;

int main()
{
    String s = "ababax";

    cout << s.indexOf("bax") << endl;

    return 0;
}

        编译运行结果如下

KMP 算法的应用(二十七)

        我们看到返回的位置为下标为 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 <iostream>
#include <cstring>
#include "DTString.h"

using namespace std;
using namespace DTLib;

int main()
{
    String s = "ababax";

    cout << s.remove("bab").str() << endl;

    return 0;
}

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

KMP 算法的应用(二十七)

        3、字符串的减法操作定义(operator -)

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

KMP 算法的应用(二十七)

            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 <iostream>
#include <cstring>
#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 应该为空,我们来看看结果

KMP 算法的应用(二十七)

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

        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 <iostream>
#include <cstring>
#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,运行结果如下

KMP 算法的应用(二十七)

        5、从字符串中创建子串

            String sub(int i, int len) const;

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

KMP 算法的应用(二十七)

        具体源码实现如下

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<char*>(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 <iostream>
#include <cstring>
#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" ; 运行结果如下

KMP 算法的应用(二十七)

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

原创文章,作者:奋斗,如若转载,请注明出处:https://blog.ytso.com/187298.html

(0)
上一篇 2021年11月5日
下一篇 2021年11月5日

相关推荐

发表回复

登录后才能评论