这是以前学数据结构时写的代码。用的是类。
其中 int Find( const String& pat ) const;
是查找当前String类的对象this中是否还有pat字符串;时间复杂度O(n^2)
int KMP_Find( const String& pat ) const;是改进的KMP模式匹配算法
时间复杂度O(n),哈哈,KMP算法比较难度,但确实是经典算法,建议找本数据结构的参考书。
//string.h文件
#ifndef STRING_H
#define STRING_H
#include <iostream>
#include <cstdio>
#include <cstring>
class String{
public:
String();
String( const char* init );
String( const String& init );
~String();
int Length() const;
int Find( const String& pat ) const;
int KMP_Find( const String& pat ) const;
String operator ()( int pos, int len );
int operator ==( const String& ob ) const;
int operator !=( const String& ob ) const;
int operator !() const;
String& operator =( const String& ob );
String& operator +=( const String& ob );
char& operator []( const int i ) const;
void Print();
private:
int curlen;
char* ch;
static const int MAXLEN;
};
#endif
//string.cpp文件
#include "string.h"
const int String::MAXLEN = 5000;
String::String()
{
ch = new char[ MAXLEN+1 ];
if( ch = NULL )
{
std::cerr << "Allocation Error!" << std::endl;
exit( 1 );
}
ch[ 0 ] = '\0';
curlen = 0;
}
String::String( const char* init )
{
// 检查长度是否合法
int init_len = strlen( init );
if( init_len > MAXLEN )
{
std::cerr << "the string is out of range!" << std::endl;
exit( 1 );
}
ch = new char[ MAXLEN+1 ];
if( ch == NULL )
{
std::cerr << "Allocation Error!" << std::endl;
exit( 1 );
}
strcpy( ch, init );
curlen = init_len;
}
String::String( const String& init )
{
ch = new char[ MAXLEN+1 ];
if( ch == NULL )
{
std::cerr << "Allocation Error!" << std::endl;
exit( 0 );
}
strcpy( ch, init.ch );
curlen = init.curlen;
}
String::~String()
{
delete []ch;
}
int String::Length() const
{
return curlen;
}
int String::Find( const String& pat ) const
{
char* p = pat.ch;
char* s = ch;
int pat_iterator = 0;
if( pat.curlen > 0 && curlen >= pat.curlen )
{
while( pat_iterator < curlen-pat.curlen )
{
if( *p == *s )
{
p++;
s++;
if( *p == '\0' ) return pat_iterator;
}
else
{
pat_iterator ++;
p = pat.ch;
s = ch + pat_iterator;
}
}
}
return -1;
}
int String::KMP_Find( const String& pat ) const
{
// 定义辅助数组,储存失效函数
int* f = new int[ pat.curlen ];
f[ 0 ] = -1;
for( int j = 1; j < pat.curlen; j++ )
{
int i = f[ j-1 ];
while( *(ch+j) != *(ch+i+1) && i >= 0 ) i = f[ i ];
if( *(ch+j) == *(ch+i+1) ) f[ j ] = i + 1;
else f[ j ] = -1;
}
// KMP算法查找
int pos_p = 0;
int pos_t = 0;
int length_p = pat.curlen;
int length_t = curlen;
while( pos_p < length_p && pos_t < length_t )
{
if( pat.ch[ pos_p ] == ch[ pos_t ] )
{
pos_p ++;
pos_t ++;
}
else
{
if( pos_p == 0 ) pos_t ++;
else pos_p = f[ pos_p-1 ] + 1;
}
}
delete []f;
if( pos_p < length_p ) return -1;
else return pos_t - length_p;
}
String String::operator ()( int pos, int len )
{
String temp;
if( pos >= 0 && len > 0 && pos + len -1 < MAXLEN && pos < curlen )
{
if( pos + len - 1 >= curlen )
{
len = curlen - pos;
}
temp.curlen = len;
for( int i = 0; i < len; i++ )
{
temp.ch[ i ] = ch[ pos+i ];
}
temp.ch[ len ] = '\0';
}
return temp;
}
int String::operator ==( const String& ob ) const
{
return ( strcmp( ch, ob.ch ) == 0 );
}
int String::operator !=( const String& ob ) const
{
return ( strcmp( ch, ob.ch ) != 0 );
}
int String::operator !() const
{
return ( curlen == 0 );
}
String& String::operator =( const String& ob )
{
if( &ob != this )
{
delete []ch;
ch = new char[ MAXLEN+1 ];
if( ch == NULL )
{
std::cerr << "Allocation Error!" << std::endl;
exit( 1 );
}
curlen = ob.curlen;
strcpy( ch, ob.ch );
}
else std::cout << "Attempted assignment of a String to itself! " << std::endl;
return *this;
}
String& String::operator +=( const String& ob )
{
curlen += ob.curlen;
if( curlen > MAXLEN )
{
std::cerr << "Out of Range!" << std::endl;
curlen = 0;
ch[ 0 ] = '\0';
}
else
{
char* temp = ch;
ch = new char[ MAXLEN+1 ];
if( ch == NULL )
{
std::cerr << "Allocation Error!" << std::endl;
exit( 1 );
}
strcpy( ch, temp );
strcat( ch, ob.ch);
delete []temp;
}
return *this;
}
char& String::operator []( const int i ) const
{
if( i < 0 || i >= curlen )
{
std::cout << "Out of Boundary!" << std::endl;
exit( 1 );
}
return ch[ i ];
}
void String::Print()
{
for( int i = 0; i < curlen; i++ )
{
std::cout << ch[ i ];
}
std::cout << std::endl;
}