//Test is T60_67.cpp

#include <string.h>
#include <iostream.h>

const int maxLen = 128;			//字符串的最大長度

class String {
	//對(duì)象: 零個(gè)或多個(gè)字符的一個(gè)有限序列。
public:
    String ( const String & ob);		//復(fù)制構(gòu)造函數(shù), 由一個(gè)已有的字符串對(duì)象ob構(gòu)造一個(gè)新字符串。
    String ( const char *init );		//構(gòu)造函數(shù), 構(gòu)造一個(gè)最大長度為maxLen, 由init初始化的新字符串。
    String ( );					//構(gòu)造函數(shù), 構(gòu)造一個(gè)最大長度為maxLen, 實(shí)際長度為0的字符串。
    ~String ( ) { delete [ ] ch, f; }		//析構(gòu)函數(shù)，釋放動(dòng)態(tài)分配的串空間。
    int Length ( ) const { return curLen; }		//函數(shù)返回串*this的長度。
    int String::fastFind ( String & pat ) const;
    void String::fail ( );
    String &operator ( ) ( int pos, int len );
	 //當(dāng) 0<=pos<=maxLen且0(len且pos+len<maxLen 時(shí), 則在串*this中從pos所指出
	 //位置開始連續(xù)取len個(gè)字符組成子串返回。
    int operator == ( const String &ob ) const { return strcmp (ch, ob.ch) == 0; }
	 //判是否串相等。若串*this與ob相等, 則函數(shù)返回1, 否則函數(shù)返回0。
    int operator != ( const String &ob ) const { return strcmp (ch, ob.ch) != 0; }
	 //判是否串不相等。若串*this與ob不相等, 則函數(shù)返回1, 否則函數(shù)返回0。
    int operator ! ( ) const { return curLen == 0; }
	 //判是否串空。若串*this為空, 則函數(shù)返回1, 否則函數(shù)返回0。
    String &operator = ( const String & ob );
	 //串ob賦值給當(dāng)前串*this
    String &operator += ( const String & ob );
	 //若 length(*this)+length(ob)<=maxLen, 則把串ob接在串*this后面。
    char &operator [ ] ( int i );
	 //取*this的第i個(gè)字符。
    int Find ( String &pat ) const;
	 //若串pat與串*this中的某個(gè)子串匹配, 則函數(shù)返回第1次匹配時(shí)子串在串*this中的
	 //位置。若串pat為空或在串*this中沒有匹配子串, 則函數(shù)返回-1。
    friend ostream & operator << (ostream& out , String s);
private:
    int curLen, *f ;								//串的長度
    char *ch;									//串存放數(shù)組
};

#include <iostream.h>
#include <process.h>

String::String ( const String &ob ) {					//串復(fù)制構(gòu)造函數(shù)
    ch = new char[maxLen+1];						//創(chuàng)建字符串?dāng)?shù)組
    if ( !ch ) { cout << "Allocation Error\n";  exit(1); }
    curLen = ob.curLen;							//串長度
    strcpy ( ch, ob.ch );							//串復(fù)制
}

String::String ( const char *init ) {						//串構(gòu)造函數(shù)
    ch = new char[maxLen+1];						//創(chuàng)建字符串?dāng)?shù)組
    if ( !ch ) { cout << "Allocation Error\n";  exit(1); }
    curLen = strlen (init);							//串長度
    strcpy ( ch, init );								//串復(fù)制
}

String::String ( ) {								//串構(gòu)造函數(shù)
    ch = new char[maxLen+1];						//創(chuàng)建字符串?dāng)?shù)組
    if ( !ch ) { cout << "Allocation Error\n";  exit(1); }
    curLen = 0;								//串長度
    ch[0] = '\0';								//空串
}

String &String::operator ( ) ( int pos, int len ) { 				//求子串
    String *temp = new String;						//創(chuàng)建一個(gè)空串
    if ( pos < 0 || pos+len-1 >= maxLen || len < 0 ) {			//參數(shù)不合理，不取子串
       temp->curLen = 0;  temp->ch[0] = '\0';
    }
    else {
	 if ( pos+len-1>=curLen ) len = curLen - pos;			//子串字符數(shù)不夠，取一部分
	 temp->curLen = len;
	 for ( int i=0, j=pos; i<len; i++, j++ ) temp->ch[i] = ch[j];
	 temp->ch[len] = '\0';
    }
    return *temp;
}

String &String::operator = ( const String &ob )	{			//串重載操作: 串賦值
    if ( &ob != this ) {							//若兩個(gè)串相等為自我賦值
	delete [ ] ch;								//刪去當(dāng)前串
	ch = new char [maxLen+1];						//重新分配，加一個(gè)字符放"\0"
	if ( ! ch ) {	cerr << "Out Of Memory!\n ";  exit (1);	}	//ch為空，分配失敗
	curLen = ob.curLen;
	strcpy ( ch, ob.ch );							//復(fù)制
    }
    else  cout << "Attempted assignment of a String to itself!\n";
    return *this;
}

String &String::operator += ( const String &ob ) { 			//串重載操作: 串連接
    char * temp =ch;								//保存將要覆蓋字符串的地址
    curLen += ob.curLen;							//結(jié)果串的長度
    ch = new char [maxLen+1];						//為結(jié)果串分配存儲(chǔ)
    if ( ! ch ) { cerr << "Out Of Memory!\n ";  exit (1) ; }
    strcpy ( ch, temp );							//結(jié)果串的前一部分
    strcat ( ch, ob.ch );							//結(jié)果串的后一部分
    delete [ ] temp;  return *this;						//釋放舊存儲(chǔ)，返回結(jié)果串
}

char &String::operator [ ] ( int i ) {					//取*this的第i個(gè)字符
    if ( i < 0 && i >= curLen ) { cout << "Out Of Boundary!\n ";  exit (1) ; }
    return ch[i];
}

int String::Find ( String &pat ) const {

//若在串s(*this)中找不到與串pat匹配的子串, 則函數(shù)返回
//-1, 否則返回pat在*this中第一次匹配的位置。
     char *p = pat.ch, *s = ch;  int i = 0;		//i是開始位置
     if ( *p && *s )					//兩個(gè)串均不空
	while ( i <= curLen - pat.curLen )
	     if ( *p++ == *s++ ) {
		  if ( !*p ) return i;	  		//串pat掃描完, *p = 0
	     }						//匹配成功
	     else { i++;  s = ch+i;  p = pat.ch; }		//不匹配
	     //s指針進(jìn)1, p指針回到開始位置做下一趟比較
     return -1;			//pat為空或在s中找不到它   		  圖2.14  程序2.13的匹配過程
}

int String::fastFind ( String & pat ) const {
     int posP = 0,  posT = 0;					//兩個(gè)串的掃描指針
     int lengthP = pat.curLen,  lengthT = curLen;			//模式與目標(biāo)串的長度
     while ( posP < lengthP && posT < lengthT )			//對(duì)兩串掃描
	 if ( pat.ch[posP] == ch[posT] ) {				//對(duì)應(yīng)字符匹配
	    posP++;  posT++;
	 }
	 else if ( posP == 0 ) posT++;
	      else posP = pat.f [posP-1]+1;
     if ( posP < lengthP ) return -1;					//匹配失敗
     else return posT - lengthP;					//匹配成功
}

void String::fail ( ) {								//對(duì)模式p(*this), 計(jì)算失效函數(shù)
    int lengthP = curLen;
    f [0] = -1;
    for ( int j=1; j<lengthP; j++ ) {					//計(jì)算f [j]
	int i = f [j-1];
	while ( *(ch+j) != *(ch+i+1) && i >= 0 ) i = f [i];		//遞推計(jì)算f [j]
	if ( *(ch+j) == *(ch+i+1) ) f [j] = i+1;
	else f [j] = -1;
    }
}

ostream & operator << ( ostream & out, String s ) {
    if ( s.curLen == 0 ) out << "It is empty!";
    else {
	 for (int i=0 ; i < s.curLen ; i++ ) out << s.ch[i];
    }
    return out;
}