42_KMP算法的应用

关键词：字符串类中的新功能、子串查找indexOf、在字符串中将指定的子串删除remove、 字符串的减法操作（重载operator-）、字符串中的子串替换replace、从字符串中创建子串sub

0. 字符串类中的新功能

成员函数	功能描述
indexOf(s)	查找子串s在字符串中的位置
remove(s)	将字符串中的子串s删除
operator - (s)	定义字符串减少
replace(s, t)	将字符串的子串s替换为t
sub(i, len)	从字符串中创建子串

1. 子串查找（KMP算法的直接运用）

int indexOf(const char* s) const
int indexOf(const String& s) consts

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

int indexOf(const String& s) const
{
    return kmp(m_str, s.m_str);
}

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

步骤：

1. 根据KMP在目标字符串中查找子串的位置
2. 通过子串位置和子串长度进行删除

// 删除指定位置指定长度的字符串
String& String::remove(int i, int len)
{
    if( (i>=0) && (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());
}

3. 字符串的减法操作（重载operator-）

原理：使用remove实现字符串间的减法操作

• 字符串自身不被修改
• 返回产生的新串

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

4. 字符串中的子串替换

将字符串中的子串t替换成s。
步骤：

1. 通过indexOf(t)获取子串t的位置i；
2. 通过remove(t)将子串移除；
3. 在位置i插入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);
}

5. 从字符串中创建子串

String sub(int i, int len) const

• 以i为起点提取长度为len的子串
• 子串提取不会改变字符串本身的状态

String String::sub(int i, int len) const
{
    String ret;

    if( (i >= 0) && (i < m_length) )
    {
        if(len < 0) len = 0;
        if(i + len > m_length) len = m_length - i;

        char* substr = reinterpret_cast<char*>(malloc(len));

        if( substr != NULL )
        {
            strncpy(substr, m_str+i, len);

            ret = substr;
        }
        else
        {
            THROW_EXCEPTION(NoEnoughMemoryExcetion, "No memory to create sub string ...");
        }
    }
    else
    {
        THROW_EXCEPTION(IndexOutOfBoundsException, "Parameter i is invalid...");
    }

    return ret;
}

6. 小结

• 字符串类是工程开发中必不可少的组件
• 字符串中应该包含常用字符串操作函数
  • 增：insert, operator+, ...
  • 删：remove, operator-, ...
  • 查：indexOf,...
  • 改：replace, ...

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4