【正文】 [maxLen+1]。 //重新分配 if ( ch == NULL ) { cerr “內(nèi)存不足 !\n ”。 exit (1)。} curLen = 。 //串復(fù)制 strcpy ( ch, )。 } else cout “字符串自身賦值出錯 ! \n”。 return *this。 } charamp。 String :: operator [ ] ( int i ) { //按串名提取串中第 i 個字符 if ( i 0 amp。amp。 i = curLen ) { cout “串下標(biāo)超界 !\n ”。 exit (1)。 } return ch[i]。 } 例：串 st = “university”, 使用示例 newSt = st； newChar = st[1]。 數(shù)組賦值 newSt = “university” 提取字符 newChar = ?n? Stringamp。 String :: operator += ( Stringamp。 ob ) { //串連接 char * temp = ch。 //暫存原串?dāng)?shù)組 curLen += 。 //串長度累加 ch = new char [maxLen+1]。 if ( ch == NULL ) { cerr “存儲分配錯 !\n ”。 exit (1)。 } strcpy ( ch, temp )。 //拷貝原串?dāng)?shù)組 strcat ( ch, )。 //連接 ob串?dāng)?shù)組 delete [ ] temp。 return *this。 } 例：串 st1 = “beijing ”, st2 = “university”, 使用示例 st1 += st2。 連接結(jié)果 st1 = “beijing university” st2 = “university” 串的模式匹配 ? 定義 在串中尋找子串（第一個字符）在串中的位置 ? 詞匯 在模式匹配中，子串稱為 模式 ，串稱為 目標(biāo) 。 ? 示例 目標(biāo) T : “Beijing” 模式 P : “jin” 匹配結(jié)果 = 3 第 1趟 T a b b a b a 窮舉的模式 P a b a 匹配過程 第 2趟 T a b b a b a P a b a 第 3趟 T a b b a b a P a b a 第 4趟 T a b b a b a P a b a ? int String :: Find ( String amp。pat ) const { //窮舉的模式匹配 char * p = , * s = ch。 int i = 0。 if ( *p amp。amp。 *s ) //當(dāng)兩串未檢測完 while ( i = curLen ) if ( *p++ == *s++ ) //比較串字符 if ( !*p ) return i。 //相等 else { i++。 s = ch + i。 p = 。 } //對應(yīng)字符不相等，對齊目標(biāo)的 //下一位置，繼續(xù)比較 return 1。 } 目標(biāo) T t0 t1 t2 …… tm1 … tn1 ? ? ? ? 模式 pat p0 p1 p2 …… pm1 目標(biāo) T t0 t1 t2 …… tm1 tm … tn1 ? ? ? ? 模式 pat p0 p1 …… pm2 pm1 目標(biāo) T t0 t1 …… ti ti+1…… ti+m2 ti+m1… tn1 ‖ ‖ ‖ ‖ 模式 pat p0 p1 …… pm2 pm1 改進的模式匹配 ? 窮舉的模式匹配算法時間代價： 最壞情況比較 nm+1趟，每 趟比較 m次，總比較次數(shù)達 (nm+1)*m ? 原因在于 每趟重新比較時，目標(biāo)串的檢測指針要回退。改進的模式匹配算法可使目標(biāo)串的檢測指針每趟不回退。 ? 改進的模式匹配 (KMP)算法的時間代價： ? 若每趟第一個不匹配，比較 nm+1趟， 總比較次數(shù)最壞達 (nm)+m = n ? 若每趟第 m個不匹配，總比較次數(shù)最壞亦達到 n T t0 t1 … ts1 ts ts+1 ts+2 … ts+j1 ts+j ts+j+1 … tn1 ‖ ‖ ‖ ‖ ‖ ? P p0 p1 p2 … pj1 pj pj+1 則有 ts ts+1 ts+2 … ts+j = p0 p1 p2 … pj (1) 為使模式 P 與目標(biāo) T 匹配，必須滿足 p0 p1 p2 … pj1 … pm1 = ts+1 ts+2 ts+3 … ts+j … ts+m 如果 p0 p1 … pj1 ? p1 p2 … pj (2) 則立刻可以斷定 p0 p1 … pj1 ? ts+1 ts+2 … ts+j 下一趟必不匹配 同樣，若 p0 p1 … pj2 ? p2 p3 … pj 則再下一趟也不匹配，因為有 p0 p1 … pj2 ? ts+2 ts+3 … ts+j 直到對于某一個“ k”值，使得 p0 p1 … pk+1 ? pjk1 pjk … pj 且 p0 p1 … pk = pjk pjk+1 … pj 則 p0 p1 … pk = ts+jk ts+jk+1 … ts+j ‖ ‖ ‖ pjk pjk+1 … pj k 的確定方法 當(dāng)比較到模式第 j 個字符失配時， k 的 值 與模式的前 j 個字符有關(guān)，與目標(biāo)無關(guān)。 利用失效函數(shù) f (j)可描述。 利用失效函數(shù) f (j) 的匹配處理 如果 j = 0，則目標(biāo)指針加 1，模式指針回到 p0。 如果 j 0，則目標(biāo)指針不變，模式指針回到 pf ( j1)+1。 若設(shè) 模式 P = p0 p1… pm2 pm1 ????? ????? 1,. ,0, =)(110.其它情況的最大整數(shù)且使得當(dāng)jkjkjkppppppjkkjf ?? j 0 1 2 3 4 5 6 7 PP a b a a b c a c ff (( jj )) 11 11 00 00 11 11 00 11示例 ：確定失效函數(shù) f (j) 運用 KMP算法的匹配過程 第 1趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c ? j = 1 ? j = f (j1)+1 = 0 第 2趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c ? j = 0 目標(biāo)指針加 1 第 3趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 a b a a b c a c ? j = 5 ? j = f (j1)+1 = 2 第 4趟 目標(biāo) a c a b a a b a a b c a c a a b c 模式 (a b) a a b c a c ? int String :: fastFind ( String pat ) const { //帶失效函數(shù)的 KMP匹配算法 int posP = 0, posT = 0。 int lengthP = , lengthT = curLen。 while ( posP lengthP amp。amp。 posT lengthT ) if ( [p osP] == ch[posT] ) { posP++。 posT++。 //相等繼續(xù)比較 } else if ( posP == 0 ) posT++。 //不相等 else posP = [posP1]+1。 if ( posP lengthP ) return 1。 else return posT lengthP。 } 計算失效函數(shù) f [ j ] 的方法 首先確定 f [0] = 1，再利用 f [ j]求 f [ j+1]。 其中 , f (1)[ j ] = f [ j ], f (m)[ j ] = f [f (m 1)[ j ]] ???????????? ,][][01111][)(jkppjfjfj( k )jfm 否則或的最小正整數(shù)可找到令 void String :: fail ( ) { //計算失效函數(shù) int lengthP = curLen。 f [0] = 1。 //直接賦值 for ( int j = 1。 j lengthP。 j++ ) { //依次求 f [j] int i = f [j1]。 while ( *(ch+j) != *(ch+i+1) amp。amp。 i = 0 ) i = f [i]。 //遞推 if ( *(ch+j) == *(ch+i+1) ) f [j] = i+1。 else f [j] = 1。 } }