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算法的应用(二十七)-创新互联
网页网址:http://pwwzsj.com/article/csheid.html