數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE數(shù)據(jù)結(jié)構(gòu)DATASTRUCTURE第4章數(shù)組和字符串DATASTRUCTURE引言數(shù)組在算法設(shè)計(jì)中經(jīng)常被使用，在本章中，將數(shù)組作為一種抽象數(shù)據(jù)結(jié)構(gòu)類型加以討論。在自然科學(xué)中，矩陣常被用于解決許多實(shí)際問題，在本章中介紹幾類特殊矩陣在存儲(chǔ)表示上的特點(diǎn)以及稀疏矩陣的轉(zhuǎn)置算法的實(shí)現(xiàn)。內(nèi)容提要1.介紹數(shù)組的概念2.討論數(shù)組抽象數(shù)據(jù)類型3.討論特殊矩陣的存儲(chǔ)方法4.討論稀疏矩陣的順序存儲(chǔ)方法5.討論稀疏矩陣轉(zhuǎn)置算法6.討論字符串的匹配算法4.1數(shù)組4.1.1數(shù)組抽象數(shù)據(jù)類型1.數(shù)組的定義

數(shù)組是下標(biāo)index和值value組成的偶對(duì)的集合。在數(shù)組中，每個(gè)有定義的下標(biāo)都與一個(gè)值對(duì)應(yīng)，這個(gè)值稱做數(shù)組元素。每個(gè)偶對(duì)形如：(index,value)

3

5

…

…

…01…

…

…maxLength-1(0，3)（1，5）2.數(shù)組抽象數(shù)據(jù)類型ADT4.1數(shù)組抽象數(shù)據(jù)類型ADTArray{Data:

下標(biāo)index和元素值value組成的數(shù)據(jù)對(duì)集合，其中任意兩個(gè)數(shù)據(jù)對(duì)的下標(biāo)index各不相同。

Operations:Create():

建立一個(gè)數(shù)組。

Retrieve(i):返回下標(biāo)為i的元素值。

Store(i,x):將下標(biāo)為i的數(shù)據(jù)對(duì)的值置為x。};4.1.2數(shù)組的順序表示

數(shù)組通常采用順序表示：1.一維數(shù)組的順序表示2.二維數(shù)組的順序表示3.多維數(shù)組的順序表示

第四章數(shù)組和字符串4.1 數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2 特殊矩陣4.3稀疏矩陣設(shè)第一個(gè)數(shù)組元素a[0]的存儲(chǔ)地址是loc(a[0])，若已知每個(gè)數(shù)組元素占k個(gè)存儲(chǔ)單元，則下標(biāo)為i的數(shù)組元素a[i]的存儲(chǔ)地址loc(a[i])為

loc(a[i])=loc(a[0])+i*k(i=0,1,2,…,n-1)。1.一維數(shù)組的順序表示2.二維數(shù)組的順序表示

二維數(shù)組a[m][n]映射到一維的存儲(chǔ)空間時(shí)有兩種順序：行優(yōu)先和列優(yōu)先。大多數(shù)語言如PASCAL、BASIC、C、C++等都是按行優(yōu)先順序存儲(chǔ)的，F(xiàn)ORTRAN是按列優(yōu)先順序存儲(chǔ)的。a[0][0]a[0][1]…a[0][n-1]a[1][0]a[1][1]…a[1][n-1]…a[m-1][0]a[m-1][1]…a[m-1][n-1]

下標(biāo)為0的行

下標(biāo)為1的行

…

下標(biāo)為n-1的行

(a)行優(yōu)先的順序表示

行優(yōu)先順序的地址計(jì)算：若對(duì)于二維數(shù)組a[m][n],已知每個(gè)數(shù)組元素占k個(gè)存儲(chǔ)單元，第一個(gè)數(shù)組元素a[0][0]的存儲(chǔ)地址是loc(a[0][0]),則數(shù)組元素a[i][j]的存儲(chǔ)地址loc(a[i][j])為loc(a[i][j])=loc(a[0][0])+(i*n+j)*k

(0

i<m;0

j<n)

a[0][0]a[0][1]…a[0][n-1]a[1][0]a[1][1]…a[1][n-1]…a[m-1][0]a[m-1][1]…a[m-1][n-1]

列優(yōu)先順序存儲(chǔ)的地址計(jì)算：loc(a[i][j])=loc(a[0][0])+(j*m+i)*k(0

i<m;0

j<n)a[0][0]a[1][0]…a[m-1][0]a[0][1]a[1][1]…a[m-1][1]…a[0][n-1]a[1][n-1]…a[m-1][n-1]

下標(biāo)為0的列

下標(biāo)為1的列

…

下標(biāo)為n-1的列

(b)列優(yōu)先的順序表示例1：10×10的整型數(shù)組A，其每個(gè)數(shù)組元素占2個(gè)字節(jié)，已知A[0][0]在內(nèi)存中的地址是100，按行優(yōu)先，A[4][6]的地址是

。A．228B．192C．124D．138loc(a[0][0])+(i×n+j)×k＝100+（4*10+6）*2＝192

推廣到多維數(shù)組a[m1][m2]…[mn]，數(shù)組元素a[i1][i2]…[in]的存儲(chǔ)地址為：loc(a[i1][i2]…[in])=loc(a[0]…[0])+(i1*m2*m3*…*mn

+i2*m3*m4*…*mn+…+in-1*mn

+in

)*k(0

ij<mj,1

j

n)3.多維數(shù)組的順序表示

第四章數(shù)組和字符串4.1 數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2 特殊矩陣4.3稀疏矩陣4.1.3一維數(shù)組的C++類

用C++的模板類定義的一維數(shù)組抽象數(shù)據(jù)類型。見程序4.1數(shù)組的C++類。這個(gè)類的共享成員函數(shù)包括構(gòu)造函數(shù)、析構(gòu)函數(shù)、下標(biāo)操作符[]和數(shù)組賦值。重載下標(biāo)操作符用來返回指向第i個(gè)元素的引用。賦值操作符實(shí)現(xiàn)數(shù)組的整體賦值。

第四章數(shù)組和字符串4.1 數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2 特殊矩陣4.3稀疏矩陣程序4.1一維數(shù)組的C++類#include<assert.h>template<classT>classArray1D{public: Array1D(intsz=0);//缺省時(shí)長(zhǎng)度為0

~Array1D(){delete[]elements;} T&operator[](inti)const;//取元素值

Array1D<T>&operator=(constArray1D<T>&r);

//整體賦值

friendistream&operator>>(istream&in,Array1D<T>&r);friendostream&operator<<(ostream&out,constArray1D<T>&r); private:

intsize; T*elements;};template<classT>Array1D<T>::Array1D(intsz){//創(chuàng)建動(dòng)態(tài)一維數(shù)組

assert(sz>=0);size=sz;elements=newT[sz];}1、構(gòu)造函數(shù)

在函數(shù)的實(shí)現(xiàn)中使用了一種斷言assert，它是C++提供的一種功能，若斷言語句的條件滿足，則繼續(xù)執(zhí)行后面的語句；否則出錯(cuò)處理，終止程序執(zhí)行。assert語句包括在assert.h中。template<classT>T&Array1D<T>::operator[](inti)const{assert(i>=0&&i<size);returnelements[i];}2、重載下標(biāo)操作符

第四章數(shù)組和字符串4.1 數(shù)組

4.1.1數(shù)組抽象數(shù)據(jù)類型

4.1.2數(shù)組的順序表示

4.1.3一維數(shù)組的C++類4.2 特殊矩陣4.3稀疏矩陣template<classT>Array1D<T>&Array1D<T>::operator=(constArray1D<T>&r){if(this!=&r){//防止自我賦值

size=r.size;delete[]elements;//釋放原空間

elements=newT[size];//重新分配空間

for(inti=0;i<size;i++)elements[i]=r.elements[i];//復(fù)制元素

}return*this;}Array1D<int>a(5),b(8);a=b;3、重載賦值操作符4、重載輸入操作符template<classT>istream&operator>>(istream&in,Array1D<T>&r){

cout<<"Intputarray\n";

for(inti=0;i<r.size;i++)in>>r.elements[i];returnin;}使用實(shí)例：Array1D<int>b(10);cin>>b;5、重載輸出操作符template<classT>ostream&operator<<(ostream&out,constArray1D<T>&r){

cout<<"Array=";

for(inti=0;i<r.size;i++)out<<r.elements[i]<<'';out<<endl;returnout;}使用實(shí)例：Array1D<int>a(5);cout<<a;程序4.2應(yīng)用一維數(shù)組類的主程序#include"array1d.h"voidmain(){Array1D<int>a(5),b(8);Array1D<int>c;//采用缺省長(zhǎng)度0

cin>>a;cout<<"a"<<a;

cin>>b;cout<<"b"<<b;

cout<<"c"<<c;

cout<<"a[0]="<<a[0]<<";"<<"b[5]="<<b[5]<<endl;c=b;cout<<"c=b,c"<<c;b=a;cout<<"b=a,b"<<b;}4.2特殊矩陣

1.對(duì)稱矩陣在n×n的矩陣A中，若aij=aji(1≤i,j≤n)，則稱其為n階對(duì)稱矩陣。對(duì)于對(duì)稱矩陣，可以只存儲(chǔ)上三角(或下三角)中的元素(包括對(duì)角線上的元素)，這樣有n2個(gè)元素的三角矩陣，只需要num=n(n+1)/2個(gè)元素的存儲(chǔ)空間，從而提高了存儲(chǔ)效率。4.2.1對(duì)稱矩陣

若用一維數(shù)組b[num]以行優(yōu)先順序存儲(chǔ)下三角(包括對(duì)角線)元素，則矩陣元素aij的下標(biāo)（i,j）和該元素在數(shù)組b中的存儲(chǔ)位置k之間有如下關(guān)系：a00a10a11a20…

aij

…an-1n-10123...num-1圖4-2對(duì)稱矩陣的存儲(chǔ)表示2、上（下）三角矩陣主對(duì)角以下元素全為0的方陣稱為上三角矩陣。主對(duì)角以上元素全為0的方陣稱為下三角矩陣。上、下三角矩陣也可以采用對(duì)稱矩陣的存儲(chǔ)方式，只存儲(chǔ)主對(duì)角線及其以上（或以下）的元素。

第四章數(shù)組和字符串4.1 數(shù)組4.2 特殊矩陣

4.2.1對(duì)稱矩陣4.3稀疏矩陣4.3稀疏矩陣稀疏矩陣大多數(shù)元素為零的矩陣稱為稀疏矩陣。

4.3.1稀疏矩陣抽象數(shù)據(jù)類型

1、稀疏矩陣的操作在稀疏矩陣上執(zhí)行的操作本質(zhì)上是普通矩陣的操作，ADT4.2定義了包括建立、加法、乘法和轉(zhuǎn)置操作的抽象數(shù)據(jù)類型。2.稀疏矩陣抽象數(shù)據(jù)類型ADT4.2稀疏矩陣抽象數(shù)據(jù)類型ADTSparseMatrix

{Data:

絕大多數(shù)元素為零的矩陣。

Operations:Create();建立一個(gè)稀疏矩陣。

Destroy()；撤消一個(gè)稀疏矩陣。

Add(B,C)：前矩陣對(duì)象與B相加，C中返回相加和。

Multiply(B,C):當(dāng)前矩陣對(duì)象與B相乘，C中返回相乘積。

Transpose(B):B中返回當(dāng)前矩陣對(duì)象的轉(zhuǎn)置矩陣。}3.稀疏矩陣的C++類程序4.2稀疏矩陣的C++類template<classT>classSparseMatrix{public:

SparseMatrix(int

maxRowSize,

int

maxColSize){};~SparseMatrix(){};virtualvoidAdd(constSparseMatrix<T>&B,

SparseMatrix<T>&C)const;virtualvoidMul(const

SparseMatrix<T>&B,

SparseMatrix<T>&C)const;virtualvoidTranspose(SparseMatrix<T>&B)const;private:

int

maxRows,maxCols;};4.3.2稀疏矩陣的順序表示

1.三元組表示法按照壓縮存儲(chǔ)的思想，稀疏矩陣Am

n中的每一個(gè)非零元素aij的行號(hào)、列號(hào)和值可以用一個(gè)三元式(i,j,v)表示。三元式可以按行或按列的順序存儲(chǔ)在一維數(shù)組中，形成三元組。

第四章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣

4.3.1抽象數(shù)據(jù)類型

4.3.2稀疏矩陣順序表示

4.3.3稀疏矩陣轉(zhuǎn)置為了節(jié)省空間，對(duì)于稀疏矩陣可只存非零元素。2.三元組按行順序存儲(chǔ)圖4-3稀疏矩陣及其行三元組表示及關(guān)系三元式(a)稀疏矩陣M(b)M的列三元組程序4.3Term類template<classT>structTerms

{//定義三元式

introw,col;Tvalue;};C++將結(jié)構(gòu)擴(kuò)展成類，結(jié)構(gòu)成為類的一種特例。3.三元組的Term類程序4.3行三元組表示的稀疏矩陣的C++類template<classT>classSeqTriple{public:

SeqTriple(int

maxLengthSize);

SeqTriple<T>Add(SeqTriple<T>b);

SeqTriple<T>Multiply(SeqTriple<T>b);

SeqTriple<T>Transpose();private:

int

maxSize;//最大個(gè)數(shù)

int

cols,rows，Nonzeros;//行數(shù)，列數(shù)，非零個(gè)數(shù)

Terms<T>

*trip;//指向三元組};4.行三元組表示的稀疏矩陣的C++類(a)稀疏矩陣MNonzeros=8rows=cols=稀疏矩陣的數(shù)據(jù)成員1.矩陣轉(zhuǎn)置4.3.2稀疏矩陣轉(zhuǎn)置

2.普通矩陣轉(zhuǎn)置

普通的二維數(shù)組存儲(chǔ)下，矩陣轉(zhuǎn)置運(yùn)算的程序段為：for(inti=0;i<m;i++)for(intj=0;j<n;j++)B[j][i]=A[i][j];

即將矩陣中的元素A[i][j]賦值給轉(zhuǎn)置矩陣中的元素B[j][i]。

時(shí)間復(fù)雜度為O(m×n)。

第四章數(shù)組和字符串4.1數(shù)組4.2特殊矩陣4.3稀疏矩陣

4.3.1抽象數(shù)據(jù)類型

4.3.2稀疏矩陣順序表示

4.3.3稀疏矩陣轉(zhuǎn)置方法三:快速轉(zhuǎn)置算法

快速轉(zhuǎn)置算法通過增加適量的存儲(chǔ)空間，達(dá)到節(jié)省時(shí)間的目的?？焖俎D(zhuǎn)置算法使用n個(gè)指針k[n](n是矩陣的列數(shù))，指向A中每一列的第一個(gè)非零元素在T中的存放位置。轉(zhuǎn)置矩陣行三元組轉(zhuǎn)置矩陣的行三元組轉(zhuǎn)置矩陣行三元組轉(zhuǎn)置矩陣的行三元組行三元組轉(zhuǎn)置矩陣的行三元組轉(zhuǎn)置矩陣關(guān)系快速轉(zhuǎn)置算法基本步驟：

(1)計(jì)算每列非零元素個(gè)數(shù)，存入num中

(2)計(jì)算每列第一非零元素在新的行三元組中的位置，存入k中

(3)快速轉(zhuǎn)置快速轉(zhuǎn)置算法基本步驟：

(1)計(jì)算num，num數(shù)組用于存放每列的非零元素個(gè)數(shù)

rowcolvalue0016032205-16111212323-84091621501234567num[0]++->1num[3]++->1num[5]++->1num[1]++->1num[2]++->1num[3]++->2num[0]++->2num[2]++->2

col012345num[col]212201

k[col]023577表4-1num數(shù)組和k數(shù)組num[i]初始值為0。計(jì)算num[i]時(shí)也只需對(duì)三元組的COL掃描一遍。

顯然k[0]=0。計(jì)算k[i]時(shí)，可先考慮計(jì)算每一列中非零元素的個(gè)數(shù)num[i],得到如下計(jì)算公式：k[0]=0k[i]=k[i-1]+num[i-1](1≤i≤n)

col012345num[col]212201

k[col]023577表4-1num數(shù)組和k數(shù)組快速轉(zhuǎn)置算法基本步驟：

(2)計(jì)算k，存放每列第一非零元素在新的行三元組中的位置

2615213111230220123456701234567rowcolvalue

50-16

32-800160491rowcolvalue0016032205-16111212323-840916215k[0]=0k[3]=5k[5]=7k[1]=2k[2]=3k[3]=6k[0]=1k[4]=5k[3]=5k[5]=7k[1]=2k[2]=3k[4]=7k[0]=0(3)快速轉(zhuǎn)置快速轉(zhuǎn)置算法程序4.6稀疏矩陣的快速轉(zhuǎn)置template<classT>voidSeqTriple<T>::Transpose(SeqTriple<T>&B)const{

int*num=newint[n];int*k=newint[n];B.m=n;B.n=m;B.t=t;if(t>0){for(inti=0;i<n;i++)num[i]=0;//初始化numfor(i=0;i<t;i++)num[trip[i].col]++;//計(jì)算numk[0]=0;for(i=1;i<n;i++)k[i]=k[i-1]+num[i-1];//計(jì)算kfor(i=0;i<t;i++){

intj=k[trip[i].col]++;//trip第i項(xiàng)在B.trip中的位置j

B.trip[j].row=trip[i].col;

B.trip[j].col=trip[i].row;

B.trip[j].value=trip[i].value;}}delete[]num;delete[]k;}O(n+t)26152131112302201234567

50-16

32-800160491rowcolvalue0016032205-16111212323-840916215

col012345num[col]212201

k[col]023577表4-1num數(shù)組和k數(shù)組trip4.4字符串

4.4.1字符串ADT字符串的定義字符串(簡(jiǎn)稱為串)是由n(

0)個(gè)字符組成的有限序列。S=“a0a1…an－1”(n≥0)其中，S是串名，單引號(hào)括起來的字符序列是串S的值。n是串中字符個(gè)數(shù)，又稱串長(zhǎng)度，n=0的串稱為空串。要注意區(qū)分空串和空白串。

串中任意連續(xù)個(gè)字符組成的子序列稱為該串的子串，包含子串的串稱為主串。通常以子串的首字符在主串中的位置作為子串在主串中的位置。例如：

S=‘a(chǎn)bcaabcbcde’P=‘a(chǎn)abc’S為主串，P為子串ADTString{數(shù)據(jù)：

字符串是由n(≥0)個(gè)字符組成的有限序列S="a0a1…an-1"，0

i<n。

運(yùn)算：

Create():建立一個(gè)空串。

Destroy():撤消一個(gè)串。

Length():返回當(dāng)前串對(duì)象的長(zhǎng)度。

Clear():置為空串。

ADT４.3字符串ADT

Assign(S):串S的值賦給當(dāng)前串對(duì)象。

Concat(b):將串b連接在當(dāng)前串對(duì)象之后。

Insert(P,i):將串P插在當(dāng)前串對(duì)象的位置i處。

Delete(i,len):從當(dāng)前串對(duì)象的位置i起刪除len個(gè)字符。

Substr(i,len):返回當(dāng)前串對(duì)象中，從位置i開始的len個(gè)字符組成的子串。

Find(i,P):返回子串P在當(dāng)前串對(duì)象中的位置。若當(dāng)前串對(duì)象不包含串P，則返回-1。}1.鏈接存儲(chǔ)表示4.4.2

字符串的存儲(chǔ)表示

2.順序存儲(chǔ)表示

串的順序表示可用C++的一維字符數(shù)組來描述。#include<string.h>chars[20]="cdabcde“；#include<string.h>classString{public:String();String(constchar*p);~String(){delete[]str;};

int

Find(inti,String&P);private:

intn;//當(dāng)前串長(zhǎng)

char*str;//動(dòng)態(tài)一維字符數(shù)組的指針};String::String(constchar*p){n=strlen(p);

str=newchar[n+1];

strcpy(str,p);}4.4.3簡(jiǎn)單模式匹配算法

設(shè)有兩個(gè)字符串s和p，在串s中找串p的過程被稱為模式匹配

。這里s為主串，p為子串，又稱為模式。模式匹配最普遍的應(yīng)用是文本編輯器中查找串．如：WORD中的“Find”等命令．簡(jiǎn)單模式匹配的算法思想

１.從主串s中下標(biāo)為i的字符與模式串p的第１個(gè)字符(下標(biāo)為0)開始逐個(gè)比較，遇到不相等時(shí)，即到達(dá)失配點(diǎn)，該趟匹配失?。?s回到i加１的位置（稱為回溯），p回到第１個(gè)字符位置，開始下趟匹配．直到匹配成功返回p的第１個(gè)字符在s中的位置或者s中不存在p，匹配失?。?jiǎn)單模式匹配－匹配成功失配點(diǎn)int

String::Find(inti,String&P){ if(i<0||i>n-1){//越界檢查

cout<<"Outofbounds!"<<endl;return-1;}

char*pp=P.str,//指針pp指向模式串P

char*t=str+i;//指針t指向主串

while(*pp!='\x0'&&i<=n-P.n) if(*pp++!=*t++){//如果失配

pp=P.str;

//模式串回到第1個(gè)字符,為下趟匹配準(zhǔn)備

t=str+(++i);//主串回到i+1的位置，為下趟匹配準(zhǔn)備

}if(*pp==‘\0’)returni;

//串pp已到串尾，匹配成功

return-1;

//匹配失敗}

tpp

簡(jiǎn)單匹配算法的漸近時(shí)間復(fù)雜度：設(shè)主串和模式串的長(zhǎng)度為n和m，while循環(huán)最多進(jìn)行n-m+1趟，每趟最多比較m次，這樣總的比較次數(shù)最多是(n-m+1)×m。由于(n-m+1)×m≤(n-m+m)×m=n×m，因此簡(jiǎn)單模式匹配算法在最壞情況下的時(shí)間復(fù)雜度是O(n×m)。

S=‘a(chǎn)bcabcaadbcbcdeP=‘a(chǎn)abc’

4.4.4模式匹配的KMP算法

簡(jiǎn)單匹配算法效率不高。原因：有回溯。KMP是一種無回溯匹配算法

KMP的時(shí)間復(fù)雜度是O(n+m)。效率高的主要原因是匹配失敗時(shí)在主串中不需回朔，在子串（模式串）中也不一定要回朔到第一個(gè)字符的位置。6沒有必要沒有必要第1趟，S[4]!=P[4]，匹配失敗

第2趟，回溯到S[1]、P[0]而S[1]=P[1]，P[0]!=P[1]，可推斷出

S[1]!=P[0],所以第2趟比較沒有必要第3趟，回溯到S[2]、P[0]而S[2]=P[2]，P[0]!=P[2]第3趟沒有必要第4趟，沒有必要回溯到S[3]、P[0]而S[3]==P[3]，P[0]==P[3],所以推斷出S[3]==P[0]，因此，可從S[4]與P[1]處開始沒有必要第1趟，S[4]!=P[4]，匹配失敗

第2趟，回溯到S[1]、P[0]而S[1]=P[1]，P[0]!=P[1]，可推斷出

S[1]!=P[0],所以第2趟比較沒有必要第3趟，回溯到S[2]、P[0]而S[2]=P[2]，P[0]!=P[2]第3趟沒有必要第4趟，沒有必要回溯到S[3]、P[0]而S[3]==P[3]，P[0]==P[3],所以推斷出S[3]==P[0]，因此，可從S[4]與P[1]處開始問題的關(guān)鍵:下趟匹配開始時(shí)，模式串j回朔最少的位置。這個(gè)位置如何確定？先了解一個(gè)概念：相等的前綴子串和后綴子串例如：abcabcaKMP算法的關(guān)鍵是確定模式串p中每個(gè)字符的最大k值，K是失配時(shí)j需向前回朔得最少的位置，即下趟匹配時(shí)，j的新值為k。

設(shè)主串S=“s0,s1,s2,…,sn-1”，模式串P=“p0,p1,…,pm-1”,上一趟匹配時(shí)，失配點(diǎn)為SiPj。如果能發(fā)現(xiàn)在模式串P中有：p0p1…pk-1=pj-kpj-k+1…pj-1是串p0p1…pj-1中“最長(zhǎng)的相等的前綴子串和后綴子串”，由于SiPj，故有：pj-k…

pj-2pj-1=si-k

…

si-2si-1因此

p0…

pk-2pk-1=si-k

…

si-2si-1

下一趟就可從si

和pk

開始比較。若在上一趟匹配中，SiPjs0s1...si-jsi-j+1

……...si-k……si-1si

p0p1…pk-1……..pj-k…..pj-1pj失配完全相等如果找到pj之前字符串的最長(zhǎng)的相等的前綴子串和后綴子串(其長(zhǎng)度為Ｋ)相等相等相等s0s2...si-j.........……...si-k+1si-k……....si-1si

p0p1……….pk-1pk相等若在上一趟匹配中，SiPjs0s2...si-jsi-1

si-k

……...si-k

si-k…....…si-1si

p0p1……….pk-1pk相等所以，下一趟匹配就可從si

和pk

開始比較。即主串不回溯，模式串從下標(biāo)k位置開始回溯下一趟匹配開始6沒有必要例1第1趟，S[4]!=P[4]，匹配失敗.分析：

在失配點(diǎn)前的子串“abca”中,“a”是“最長(zhǎng)的相等的前綴子串和后綴子串”，它的長(zhǎng)度為1,即K為１。結(jié)論：因此，下趟匹配從s4和p1開始沒有必要失配點(diǎn)失配點(diǎn)前的串“abcabca”中，相同的前、后綴子串只有“a”、“abca”,其中“abca”是最長(zhǎng)的相同的前、后綴子串，所以k為４，下一趟的匹配從s[7]和p[4]開始。例２，前一趟匹配中，S[７]!=P[７]，匹配失敗.

失敗函數(shù)的定義

設(shè)有長(zhǎng)度為m的模式串p＝p0p1…pm－1,，k為相同的前、后綴子串長(zhǎng)，失敗函數(shù)的定義為：此函數(shù)的含義為：當(dāng)SiPj匹配失敗時(shí)，下一趟匹配應(yīng)當(dāng)開始的位置為f(j)。當(dāng)f(j)>=0時(shí)，下趟匹配從si和pf(j)開始當(dāng)f(j)=-1時(shí)，下趟匹配從si+1和p0開始

//不存在相同的前、后綴子串時(shí)//失敗點(diǎn)在第一個(gè)字符時(shí)從定義計(jì)算失敗函數(shù)KMP算法就容易實(shí)現(xiàn)。當(dāng)SiPj時(shí)，只需使j=f[j]，即從P[f[j]]字符開始下一趟比較；主串無需回朔。

設(shè)有主串S=“abcabcaabcabacbbac”，模式串P=“abcabcabbac

”,KMP算法匹配過程如下： i=0

i=7

第S=abcabcaabcabacbbac一P=abcabcabbac趟

j=0

j=7

S[7]

P[7]j=f[7]=4

i=7

第S=abcabcaabcabacbbac二P= abcabcabbac趟

j=4

S[7]

P[4]j=f[4]=1 i=7

第S=ab cabcaabcabacbbac三P= abcabcabbac趟

j=1

S[7]

P[1]j=f[1]=0

i=7

第S=abcabca abcabacbbac四P= abcabcabbac趟

j=0

可以改進(jìn)嗎？KMP匹配算法（假設(shè)失敗函數(shù)的值已放在數(shù)組f中）int

String::FindKMP(inti,String&P){if(i<0||i>n-1){

cout<<"Outofbounds!"<<endl;return-1;}

intj=0,m=P.n;