思考：
replace图解：
程序完善：
DTString.h：
#ifndef DTSTRING_H
#define DTSTRING_H #include "Object.h" namespace DTLib
{ class String : Object
{
protected:
char* m_str;
int m_length; void init(const char* s);
bool equal(const char* l, const char* r, int len) const; static int* make_pmt(const char* p);
static int kmp(const char* s, const char* p); public:
String();
String(char c);
String(const char* s);
String(const String& s); int length() const;
const char* str() const; bool startWith(const char* s) const;
bool startWith(const String& s) const;
bool endOf(const char* s) const;
bool endOf(const String& s) const; String& insert(int i, const char* s);
String& insert(int i, const String& s); String& trim(); int indexOf(const char* s) const;
int indexOf(const String& s) const; String& remove(int i, int len); //删除指定下标，指定长度的子串
String& remove(const char* s);
String& remove(const String& s); 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 sub(int i, int len) const; char& operator [] (int i);
char operator [] (int i) const; bool operator == (const String& s) const;
bool operator == (const char* s) const; bool operator != (const String& s) const;
bool operator != (const char* s) const; bool operator > (const String& s) const;
bool operator > (const char* s) const; bool operator < (const String& s) const;
bool operator < (const char* s) const; bool operator >= (const String& s) const;
bool operator >= (const char* s) const; bool operator <= (const String& s) const;
bool operator <= (const char* s) const; String operator + (const String& s) const;
String operator + (const char* s) const;
String& operator += (const String& s);
String& operator += (const char* s); String operator - (const char* s) const;
String operator - (const String& s) const;
String& operator -= (const char* s);
String& operator -= (const String& s); String& operator = (const String& s);
String& operator = (const char* s);
String& operator = (char c); ~String();
}; } #endif // DTSTRING_H
DTString.cpp：
#include <cstring>
#include <cstdlib>
#include "DTString.h"
#include "Exception.h" using namespace std; namespace DTLib
{ int* String::make_pmt(const char* p) // O(m)
{
int len = strlen(p); int* ret = static_cast<int*>(malloc(sizeof(int) * len)); if( ret != NULL )
{
int ll = ; ret[] = ; // 第0个元素（长度为1的字符串）的ll值为0 for(int i = ; i < len; i++)
{
//不成功的情况
while( (ll > ) && (p[ll] != p[i]) )
{
ll = ret[ll];
} // 假设最理想的情况成立
//在前一个ll值的基础行进行扩展，只需比对最后扩展的字符是否相等
//相等的话ll值加1，并写入到部分匹配表
if( p[ll] == p[i] )
{
ll++;
} ret[i] = ll; // 将ll值写入匹配表 }
} return ret;
} int String::kmp(const char* s, const char* p) //O(m) + O(n) = O(m + n)
{
int ret = -; int sl = strlen(s);
int pl = strlen(p); //子串 int* pmt = make_pmt(p); //O(m) if( (pmt != NULL) && ( < pl) && (pl <= sl))
{
for( int i = ,j = ; i < sl; i++ )
{
while( (j > ) && (s[i] != p[j]) ) // j小于等于0时要退出
{
j = pmt[j];
} if( s[i] == p[j] )
{
j++;
} if( j == pl ) // j的值如果最后就是子串的长度，意味着查找到了
{
ret = i + - pl; // 匹配成功时i的值停在最后一个匹配的字符上
break;
}
}
} free(pmt); return ret;
} void String::init(const char* s)
{
m_str = strdup(s); if( m_str )
{
m_length = strlen(m_str);
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create string object ...");
}
} bool String::equal(const char* l, const char* r, int len) const
{
bool ret = true; for(int i = ; i < len && ret; i++)
{
ret = ret && (l[i] == r[i]);
} return ret;
} String::String()
{
init("");
} String::String(const char* s)
{
init(s ? s : ""); //空指针就转换成空字符串
} String::String(const String& s)
{
init(s.m_str);
} String::String(char c)
{
char s[] = {c, '\0'}; init(s);
} int String::length() const
{
return m_length;
} const char* String::str() const
{
return m_str;
} bool String::startWith(const char* s) const
{
bool ret = ( s != NULL ); if( ret )
{
int len = strlen(s); ret = (len < m_length) && equal(m_str, s, len); } return ret;
} bool String::startWith(const String& s) const
{
return startWith(s.m_str);
} bool String::endOf(const char* s) const
{
bool ret = ( s != NULL ); if( ret )
{
int len = strlen(s); char* str = m_str + (m_length - len); ret = (len < m_length) && equal(str, s, len); } return ret;
} bool String::endOf(const String& s) const
{
return endOf(s.m_str);
} String& String::insert(int i, const char* s)
{
if( ( <= i) && (i <= m_length) )
{
if( ( s != NULL) && ( s[] != '\0' ) )
{
int len = strlen(s);
char* str = reinterpret_cast<char*>(malloc(m_length + len + )); if( str != NULL )
{
strncpy(str, m_str, i);
strncpy(str + i, s, len);
strncpy(str + i + len, m_str + i, m_length - i); str[m_length + len] = '\0'; free(m_str); m_str = str;
m_length = m_length + len;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create str object...");
}
}
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "parameter i is invalid...");
} return *this;
} String& String::insert(int i, const String& s)
{
return insert(i, s.m_str);
} String& String::trim()
{
int b = ;
int e = m_length - ; while( m_str[b] == ' ')b++;
while( m_str[e] == ' ')e--; if( b == )
{
m_str[e + ] = '\0'; m_length = e + ;
}
else
{
for(int i = ,j = b; j <= e; i++, j++)
{
m_str[i] = m_str[j];
} m_str[e - b + ] = '\0';
m_length = e - b + ;
} return *this;
} 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);
} String& String::remove(int i, int len)
{
if( ( <= 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) : );
} String& String::remove(const String& s)
{
return remove(indexOf(s), s.length());
} String& String::replace(const char* t, const char* s)
{
int index = indexOf(t); if( index >= )
{
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);
} String String::sub(int i, int len) const
{
String ret; if( ( <= i) && (i<m_length) )
{
if( len < ) len = ;
if(len + i > m_length) len = m_length - i; char* str = reinterpret_cast<char*>(malloc(len + )); strncpy(str, m_str + i, len); str[len] = '\0'; ret = str;
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "parameter i is invalid...");
} return ret;
} char& String::operator [] (int i)
{
if( ( <= i) && (i < m_length) )
{
return m_str[i];
}
else
{
THROW_EXCEPTION(IndexOutOfBoundsException, "parameter i is invalid ...");
}
} char String::operator [] (int i) const
{
return (const_cast<String&>(*this))[i];
} bool String::operator == (const String& s) const
{
return ( strcmp(m_str, s.m_str) == );
} bool String::operator == (const char* s) const
{
return ( strcmp(m_str, s ? s : "") == );
} bool String::operator != (const String& s) const
{
return !(*this == s);
} bool String::operator != (const char* s) const
{
return !(*this == s);
} bool String::operator > (const String& s) const
{
return (strcmp(m_str, s.m_str) > );
} bool String::operator > (const char* s) const
{
return (strcmp(m_str, s ? s : "") > );
} bool String::operator < (const String& s) const
{
return (strcmp(m_str, s.m_str) < );
} bool String::operator < (const char* s) const
{
return (strcmp(m_str, s ? s : "") < );
} bool String::operator >= (const String& s) const
{
return (strcmp(m_str, s.m_str) >= );
} bool String::operator >= (const char* s) const
{
return (strcmp(m_str, s ? s : "") >= );
} bool String::operator <= (const String& s) const
{
return (strcmp(m_str, s.m_str) <= );
} bool String::operator <= (const char* s) const
{
return (strcmp(m_str, s ? s : "") <= );
} String String::operator + (const String& s) const
{
return (*this + s.m_str);
} String String::operator + (const char* s) const
{
String ret; int len = m_length + strlen(s ? s : ""); char* str = reinterpret_cast<char*>(malloc(len + )); if( str )
{
strcpy(str, m_str);
strcat(str, s ? s : ""); free(ret.m_str); ret.m_str = str;
ret.m_length = len;
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create str object...");
} return ret;
} String& String::operator += (const String& s)
{
return (*this = *this + s.m_str);
} String& String::operator += (const char* s)
{
return (*this = *this + s);
} String String::operator - (const char* s) const
{
return String(*this).remove(s);
} String String::operator - (const String& s) const
{
return String(*this).remove(s);
} String& String::operator -= (const char* s)
{
return remove(s);
} String& String::operator -= (const String& s)
{
return remove(s);
} String& String::operator = (const String& s)
{
return (*this = s.m_str);
} String& String::operator = (const char* s)
{
if( m_str != s )
{
char* str = strdup(s ? s: ""); if( str )
{
free(m_str); m_str = str;
m_length = strlen(m_str);
}
else
{
THROW_EXCEPTION(NoEnoughMemoryException, "No memory to create str object...");
}
} return *this;
} String& String::operator = (char c)
{
char s[] = {c, '\0'}; return (*this = s);
} String::~String()
{
free(m_str);
} }
小结：