KMP 算法的應(yīng)用（二十七）

        我們?cè)谏瞎?jié)博客中講到了 KMP 算法的具體實(shí)現(xiàn)，那么我們本節(jié)就來看看 KMP 算法的應(yīng)用。問題：如何在目標(biāo)字符串中查找是否存在指定的子串？

        我們來看看字符串類中的新功能，如下圖所示

       1、子串查找（KMP  算法的直接應(yīng)用）

            int indexOf(const char* s) const;

            int indexOf(const String& s) const;

        我們來看看具體源碼的實(shí)現(xiàn)，如下

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

        直接利用我們上節(jié)博客實(shí)現(xiàn)的 kmp 函數(shù)就能實(shí)現(xiàn) indexOf 函數(shù)，我們來看看效果

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

        編譯運(yùn)行結(jié)果如下

        我們看到返回的位置為下標(biāo)為 3 處，也就是 s[3] 處。

        2、在字符串中將指定的子串刪除

            String& remove(int i, int len);

            String& remove(const char* s);

            String& remove(const String& s);

        根據(jù) KMP 在目標(biāo)字符串中查找子串的位置，再通過子串位置和子串長(zhǎng)度進(jìn)行刪除。具體源碼實(shí)現(xiàn)如下

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

        我們來寫個(gè)測(cè)試代碼進(jìn)行測(cè)試，如下

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

        我們來看看結(jié)果是不是 aax，如下

        3、字符串的減法操作定義（operator -）

        使用 remove 實(shí)現(xiàn)字符串間的減法操作，必須得保證字符串自身不被修改，返回產(chǎn)生的新串。最后效果如下

            String operator - (const String& s) const;

            String operator - (const char* s) const;

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

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

        利用原有的 + 操作符進(jìn)行改裝即可，源碼實(shí)現(xiàn)如下

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

        我們來測(cè)試下，測(cè)試代碼如下

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

        我們來看看運(yùn)行結(jié)果，s1 = "aba", 最后的 s 應(yīng)該為空，我們來看看結(jié)果

        我們看到結(jié)果正如我們所分析的那樣。

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

        我們來看看具體源碼的實(shí)現(xiàn)

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

        我們來寫個(gè)測(cè)試代碼進(jìn)行測(cè)試，代碼如下

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

        我們來看看最后的結(jié)果是不是 axyzx，運(yùn)行結(jié)果如下

        5、從字符串中創(chuàng)建子串

            String sub(int i, int len) const;

        以 i 為起點(diǎn)提取長(zhǎng)度為 len 的子串，子串提取保證不會(huì)改變字符串本身的狀態(tài)。如下

        具體源碼實(shí)現(xiàn)如下

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

        我們來寫個(gè)測(cè)試代碼進(jìn)行測(cè)試，測(cè)試代碼如下

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

        最后的結(jié)果應(yīng)該是 s = "ababax" ; s1 = "bax" ; s3 = "aba" ; 運(yùn)行結(jié)果如下

        現(xiàn)在我們的字符串類已經(jīng)實(shí)現(xiàn)的有點(diǎn)規(guī)模了。通過今天對(duì)字符串類的學(xué)習(xí)，總結(jié)如下：1、字符串類是工程開發(fā)中必不可少的組件；2、字符串中應(yīng)該包含常用的字符串操作函數(shù)，a> 增：insert， operator + ， ...； b> 刪：remove，operator -，...； c> 查：indexOf，...； d> 改：replace，... 。