數(shù)據(jù)結(jié)構與算法 字符串

1、數(shù)據(jù)結(jié)構與算法數(shù)據(jù)結(jié)構與算法第三章第三章 字符串字符串主講人主講人 張銘張銘 :/北京大學信息科學與技術學院北京大學信息科學與技術學院網(wǎng)絡與信息系統(tǒng)研究所網(wǎng)絡與信息系統(tǒng)研究所版權所有，轉(zhuǎn)載或翻印必究版權所有，轉(zhuǎn)載或翻印必究主要內(nèi)容主要內(nèi)容n3.1 字符串抽象數(shù)據(jù)類型字符串抽象數(shù)據(jù)類型n3.2 字符串的存儲結(jié)構和類定義字符串的存儲結(jié)構和類定義n3.3 字符串運算的算法實現(xiàn)字符串運算的算法實現(xiàn)n3.4 字符串的模式匹配字符串的模式匹配字符串抽象數(shù)據(jù)類型字符串抽象數(shù)據(jù)類型 n3.1.1 基本概念基本概念n3.1.2 String抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型3.1.1 基本概念基本概念n字符串，由字符串，

2、由0個或多個字符的順個或多個字符的順序排列所組成的復合數(shù)據(jù)結(jié)構，序排列所組成的復合數(shù)據(jù)結(jié)構，簡稱簡稱“串。串。n串的長度：一個字符串所包含的串的長度：一個字符串所包含的字符個數(shù)。字符個數(shù)。n空串：長度為零的串，它不包含空串：長度為零的串，它不包含任何字符內(nèi)容。任何字符內(nèi)容。字符串常數(shù)和變量字符串常數(shù)和變量n字符串常數(shù)字符串常數(shù)n例如：例如： nn字符串變量字符串變量3.1.1.2 字符字符n字符字符(char) ：組成字符串的基：組成字符串的基本單位本單位 。n在在C和和C中中n單字節(jié)單字節(jié)8 bitsn采用采用ASCII碼對碼對128個符號字個符號字符集符集charset進行編碼進行編碼 3

3、.1.1.3 字符的編碼順序字符的編碼順序 n為了字符串間比較和運算的便利，為了字符串間比較和運算的便利，字符編碼表一般遵循約定俗成的字符編碼表一般遵循約定俗成的“偏序編碼規(guī)那么。偏序編碼規(guī)那么。n字符偏序：根據(jù)字符的自然含義，字符偏序：根據(jù)字符的自然含義，某些字符間兩兩可以比較次序。某些字符間兩兩可以比較次序。n其實大多數(shù)情況下就是字典序其實大多數(shù)情況下就是字典序n中文字符串有些特例，例如中文字符串有些特例，例如“筆劃筆劃序序3.1.1.4 C+標準標準string n標準字符串：將標準字符串：將C+的的函數(shù)庫作為字符串函數(shù)庫作為字符串數(shù)據(jù)類型的方案。數(shù)據(jù)類型的方案。n例如：例如：char

4、SM;n串的結(jié)束標記：串的結(jié)束標記：0n0是是ASCII碼中碼中8位位BIT全全0碼，碼，又稱為又稱為NULL符。符。3.1.1.4 C+標準標準string(續(xù)續(xù))n1. 串長函數(shù)串長函數(shù) int strlen(char *s);n2. 串復制串復制 char *strcpy(char *s1, char*s2);n3串拼接串拼接 char *strcat(char *s1, char *s2);n4串比較串比較 int strcmp(char *s1, char *s2);3.1.1.4 C+標準標準string(續(xù)續(xù))n5輸入和輸出函數(shù)輸入和輸出函數(shù)n6定位函數(shù)定位函數(shù) char *st

5、rchr(char *s, char c);n7右定位函數(shù)右定位函數(shù) char *strrchr(char *s, char c); 3.1.1.4 C+標準標準string(續(xù)續(xù))3.1.2 String抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型n字符串類字符串類class String：n不采用不采用char SM的形式的形式n而采用一種動態(tài)變長的存儲結(jié)構。而采用一種動態(tài)變長的存儲結(jié)構。3.1.2 String抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型(續(xù)續(xù))class String /字符串 類/它的存儲結(jié)構和實現(xiàn)方法使用了C+標準string(簡稱標準串),/為了區(qū)別,類String所派生創(chuàng)建的實例對象,簡稱本串,或?qū)嵗?/p>

6、串/在程序首,要#include 和#include 及/ 及 #include ，以及#include /1.字符串的數(shù)據(jù)表示：/字符串 S 通常用順序存放，用數(shù)組S存儲，元素的類型為char/字符串為變長，使用變量size記錄串的當前長度/ 2.使用變量訪問字符串：/字符串變量能參與運算,例如S1 + S2表示兩個字符串首尾拼接在一起/用數(shù)組str存儲字符串，在內(nèi)部可以用stri訪問串的第i個字符,/ 3.字符串類的運算集：請參看下面的成員函數(shù)private: public:char *str; /私有的指針變量，用于指向存儲向量strsize+1int size；/本串的當前實際長度St

7、ring(char *s = ); /創(chuàng)建一個空的字符串String(char *s); / 創(chuàng)建新字符串，并將標準字符串s拷貝為初值String() / 銷毀本串，從計算機存儲空間刪去本串/下面是算子的定義，包括賦值算子 拼接算子 和比較算子 等String& operator= (char *s）；/賦值操作=，標準串s拷貝到本串String& operator= (String& s）;/賦值操作=，串s復制到本串String operator (char *s）;/拼接算子，本串拼接標準串sString operator (String& s）；/拼接算子，本串拼接串sfriend S

8、tring operator+ (char *s1, String& s）；/友函數(shù)作為拼接算子+ 其返回值是一個實例串,等于標準串str拼接串s3.1.2.3 賦值算子、拼接算子賦值算子、拼接算子和比較算子和比較算子n賦值算子賦值算子n拼接算子拼接算子n比較算子比較算子 = != 和和 =3.1.2.4 輸入輸出算子輸入輸出算子 n輸入算子輸入算子n輸出算子輸出算子 3.1.2.5 處理子串處理子串(Substring)的函數(shù)的函數(shù)n簡稱簡稱“子串函數(shù)子串函數(shù)n提取子串提取子串n插入子串插入子串n尋找子串尋找子串n刪除子串刪除子串n3.1.2.6 字符串中的字符字符串中的字符n重載下標算子重

9、載下標算子 char& operator (int n);n按字符定位下標按字符定位下標 int Find(char c,int start);n反向?qū)ふ?，定位尾部出現(xiàn)的字符反向?qū)ふ?，定位尾部出現(xiàn)的字符 int FindLast(char c);3.2 字符串的存儲結(jié)構字符串的存儲結(jié)構和類定義和類定義n字符串的順序存儲字符串的順序存儲n字符串類字符串類class String的存儲結(jié)的存儲結(jié)構構字符串的順序存儲字符串的順序存儲n對于串長變化不大的字符串，可對于串長變化不大的字符串，可以有三種處理方案：以有三種處理方案：n1用用S0作為記錄串長的存作為記錄串長的存儲單元。儲單元。n缺點：限制了串

10、的最大長度不能缺點：限制了串的最大長度不能超過超過256。字符串的順序存儲字符串的順序存儲(續(xù)續(xù)) 2為存儲串的長度，另辟一為存儲串的長度，另辟一個存儲的地方。個存儲的地方。缺點：串的最大長度一般是靜態(tài)缺點：串的最大長度一般是靜態(tài)給定的，不是動態(tài)申請數(shù)組空間。給定的，不是動態(tài)申請數(shù)組空間。字符串的順序存儲字符串的順序存儲(續(xù)續(xù)) 3用一個特殊的末尾標記用一個特殊的末尾標記0。例如：例如：C+語言的語言的string函數(shù)庫函數(shù)庫include 采采用這一存儲結(jié)構。用這一存儲結(jié)構。3.2.2 字符串類字符串類class String的存儲結(jié)構的存儲結(jié)構n抽取子串函數(shù)抽取子串函數(shù) 例如：例如： St

11、ring s1 = value-; s2 = s1.Substr(2,3); 上述語句涉及的存儲形式如下上述語句涉及的存儲形式如下頁所示。頁所示。3.2.2 字符串類字符串類class String的存儲結(jié)構的存儲結(jié)構(續(xù)續(xù))3.2.2 字符串類字符串類class String的存儲結(jié)構的存儲結(jié)構(續(xù)續(xù))n微軟微軟VC的的CString類介紹類介紹n自動的動態(tài)存儲管理，串的最大長度不超過自動的動態(tài)存儲管理，串的最大長度不超過2GB n容器型容器型n不必使用不必使用new和和delete n使用特點：使用特點：n變量申明變量申明nCString s6( x, 6 ); / s6 = xxxxxx

12、nCString city = Philadelphia; / 串常數(shù)作為初值串常數(shù)作為初值n賦值語句賦值語句ns1 = s2 = hi there;n變量比較變量比較 if( s1 = s2 ) n方法調(diào)用方法調(diào)用 s1.MakeUpper(); n內(nèi)部字符比較內(nèi)部字符比較 if( s20 = h ) 3.3 字符串運算的算法實現(xiàn)字符串運算的算法實現(xiàn)n1. 串長函數(shù)串長函數(shù) int strlen(char *s);n2. 串復制串復制 char *strcpy(char *s1, char*s2);n3串拼接串拼接 char *strcat(char *s1, char *s2);n4串比較

13、串比較 int strcmp(char *s1, char *s2);3.3.1 C+標準串運算的實現(xiàn)標準串運算的實現(xiàn)n【算法【算法3-1 】字符串的復制字符串的復制char *strcpy(char *d, char *s) /這個程序的毛病是，如果字符串這個程序的毛病是，如果字符串s比字符串比字符串d要長，要長，/這個程序沒有檢查拷貝出界，沒有報告錯誤。這個程序沒有檢查拷貝出界，沒有報告錯誤。/可能會造成可能會造成d的越界的越界 int i =0; while (si != 0) di = si; i+; di = 0; return d;3.3.1 C+標準串運算的實現(xiàn)標準串運算的實現(xiàn)(

14、續(xù)續(xù))n【算法【算法3-2 】字符串的比較字符串的比較int strcmp( char *d, char *s) int i =0; while (si != 0 & di != 0 ) if (di si) return 1; else if (di = 0 & di != ch ); /當本串不含字符當本串不含字符ch，那么在串尾結(jié)束；，那么在串尾結(jié)束； /當成功尋找到當成功尋找到ch，返回該位置指針，返回該位置指針if (i = size) / 注意不是注意不是 index = size - 1n return temp; 3.3.2 String串運算的實現(xiàn)串運算的實現(xiàn)(續(xù)續(xù)) /假設

15、假設count超過自超過自index以右的實際子串長度，以右的實際子串長度， / 那么把那么把count變小變小if(count left ) count = left;/釋放原來的存儲空間釋放原來的存儲空間delete ; /張銘注釋：注意此語句！張銘注釋：注意此語句！/假設開辟動態(tài)存儲空間失敗，那么退出假設開辟動態(tài)存儲空間失敗，那么退出 = new char count+1; != 0)； /p的內(nèi)容是一個指針，的內(nèi)容是一個指針， /指向目前暫無內(nèi)容的字符數(shù)組的首字符處指向目前暫無內(nèi)容的字符數(shù)組的首字符處p = ; 3.3.2 String串運算的實現(xiàn)串運算的實現(xiàn)(續(xù)續(xù)) /q的內(nèi)容是一個

16、指針，的內(nèi)容是一個指針， /指向本實例串的指向本實例串的str數(shù)組的下標數(shù)組的下標index字符字符q = &strindex; /用用q指針取出它所指的字符內(nèi)容后，指針加指針取出它所指的字符內(nèi)容后，指針加1 / 用用p該指針所指的字符單元接受拷貝，該指針也加該指針所指的字符單元接受拷貝，該指針也加1for (i =0; i count; i+) *p+ = *q+; /循環(huán)結(jié)束后，讓的結(jié)尾為循環(huán)結(jié)束后，讓的結(jié)尾為0*p = 0; temp.size = count;return temp;3.3.2 String串運算的實現(xiàn)串運算的實現(xiàn)(續(xù)續(xù))n【算法【算法 3-12 】查找字符】查找字符n

17、int String:Find(char c,int start)n n /在本實例字符串尋找字符在本實例字符串尋找字符c，如果找到，如果找到，那么那么/將其下標位置作為整數(shù)函數(shù)值返回，如將其下標位置作為整數(shù)函數(shù)值返回，如果果/c沒有找到，那么為負值。參數(shù)沒有找到，那么為負值。參數(shù)start是下是下標，標，/從從start下標開始尋找下標開始尋找c的工作的工作,假設假設start為為/0，那么從頭尋找，那么從頭尋找nint i = start;nassert( i size); 3.3.2 String串運算的實現(xiàn)串運算的實現(xiàn)(續(xù)續(xù)) /循環(huán)跳過那些不是循環(huán)跳過那些不是c的字符的字符while

18、 (stri != 0 & stri != c ) i+; /當本串不含字符當本串不含字符c，那么尋找到串尾結(jié)束，那么尋找到串尾結(jié)束， /返回返回1表示失敗；當成功尋找到表示失敗；當成功尋找到c，返回它的，返回它的 /下標位置下標位置if (stri = 0) / 注意：不要搞成注意：不要搞成“= = return -1; else return i ; 3.4 字符串的模式匹配字符串的模式匹配n模式匹配模式匹配(pattern matching)n一個目標對象一個目標對象S字符串字符串n一個模板一個模板patternP字符串字符串n任務：用給定的模板任務：用給定的模板P，在目標字符，在目標字

19、符串串S中搜索與模板中搜索與模板P全同的一個子串，全同的一個子串，并求出并求出S中第一個和中第一個和P全同匹配的子全同匹配的子串簡稱為串簡稱為“配串，返回其首配串，返回其首字符位置。字符位置。S s0 s1 sisi+1 si+2 si+m-2 si+m-1 sn-1 P p0 p1 p2 pm -2 pm-1 p0 p1 p2 pm-1 = si si+1 si+2 si+m-1樸素模式匹配樸素模式匹配S=ababababababbP=abababb X abababb X abababb X abababb X abababb X abababb X abababb 【算法【算法3-13

20、】模式匹配原始】模式匹配原始算法其一算法其一#include “ / 不是不是 #includeint FindPat_1(String S, String P, int startindex) / 從從S末尾倒數(shù)一個模板長度位置末尾倒數(shù)一個模板長度位置 int LastIndex = () - (); if (LastIndex startindex) return (-1); /g為為S的游標，用模板的游標，用模板P和和S第第g位置子串比較，位置子串比較， /假設失敗那么繼續(xù)循環(huán)假設失敗那么繼續(xù)循環(huán) for (int g= startindex; g = LastIndex; g+) if

21、 ( P = S.Substr(g, () ) return g; /假設假設for循環(huán)結(jié)束，那么整個匹配失敗，返回值為負，循環(huán)結(jié)束，那么整個匹配失敗，返回值為負， return (-1); 3.4.1 模式匹配原始算法模式匹配原始算法(續(xù)續(xù))【算法【算法3-13】模式匹配原始算法其二】模式匹配原始算法其二int FindPat_2(String S, String P,int startindex) / 從從S末尾倒數(shù)一個模板長度位置末尾倒數(shù)一個模板長度位置 int LastIndex = () - (); /開始匹配位置開始匹配位置startindex的值過大，匹配無法成功的值過大，匹配無

22、法成功 if (LastIndex startindex) return (-1); / i 是指向是指向S內(nèi)部字符的游標，內(nèi)部字符的游標， / j 是指向是指向P內(nèi)部字符的游標內(nèi)部字符的游標 int i=startindex, j = 0;3.4.1 模式匹配原始算法模式匹配原始算法(續(xù)續(xù))/下面開始循環(huán)匹配下面開始循環(huán)匹配while (i LastIndex & j () / “ 可以嗎？可以嗎？ return (i - 1); else return -1; 3.4.1 樸素模式匹配樸素模式匹配 (糾錯糾錯)【算法【算法3-13】模式匹配原始算法糾錯】模式匹配原始算法糾錯int Find

23、Pat_2(String S, String P,int startindex) / 從從S末尾倒數(shù)一個模板長度位置末尾倒數(shù)一個模板長度位置 int LastIndex = () - P. strlen() ; /開始匹配位置開始匹配位置startindex的值過大，匹配無法成功的值過大，匹配無法成功 if (LastIndex startindex) return (-1); / i 是指向是指向S內(nèi)部字符的游標，內(nèi)部字符的游標， / j 是指向是指向P內(nèi)部字符的游標內(nèi)部字符的游標 int i=startindex, j = 0;3.4.1 樸素模式匹配糾錯樸素模式匹配糾錯(續(xù)續(xù))/下面開始

24、循環(huán)匹配下面開始循環(huán)匹配while (i() & j() ) / “=呢？呢？ if( Pj = Si) i+; j+; else i = i - j + 1; j = 0; 錯誤錯誤1：如果：如果“i LastIndex，那么后面的就匹配不到。那么后面的就匹配不到。例如，例如，abababababb abababb ()=11，()=7，LastIndex = 4;“i = 4，j = 0, 匹配匹配a，接著，接著， “i = 5，j = 1就進行不了。就進行不了。錯誤錯誤2 2： 如果如果“j =()j = () ) / “ 可以嗎？可以嗎？ return (i - j); else re

25、turn -1; 錯誤錯誤3 3： 如果如果“j j ，其實匹配結(jié)束時，正好其實匹配結(jié)束時，正好j=P.size j=P.size 因為匹配最后一個字符后，還因為匹配最后一個字符后，還j+j+出錯！出錯！其實其實 “ “j = j = 就可以！就可以！錯誤錯誤4： return (i-1); 匹配完成后，匹配完成后，i i指向指向S S中最后一個字符的下一位，中最后一個字符的下一位，減去匹配串的長度，才是開始位。減去匹配串的長度，才是開始位。3.4.1 模式匹配原始算法模式匹配原始算法(續(xù)續(xù))例如，例如，aaaaaaaaaab aaaaaab分析分析假定目標假定目標S的長度為的長度為n，模板，

26、模板P長度為長度為m， mn 在最壞的情況下，每一次循環(huán)都不成功，那么一共在最壞的情況下，每一次循環(huán)都不成功，那么一共要進行比較要進行比較n-m+1次次每一次每一次“相同匹配比較所耗費的時間，是相同匹配比較所耗費的時間，是P和和S逐逐個字符比較的時間，最壞情況下，共個字符比較的時間，最壞情況下，共m次。次。因此，整個算法的最壞時間開銷估計為因此，整個算法的最壞時間開銷估計為O(m n)。例例1， a a a a a a a a a a b a a a a a a b a a a a a a b a a a a a a b例例2， a b c d e f a b c d e f f a b c

27、d e f f a b c d e f f KMPKMP算法思想算法思想S s0 s1 si-j-1 si-j si-j+1 si-j+2 si-2 si-1 si sn-1 P p0 p1 p2 pj-2 pj -1 pj 那么有那么有 si-j si-j+1 si-j+2 si-1 = p0 p1 p2 pj-1 (1) 如果如果 p0 p1 pj-2 p1 p2 pj-1 (2) 那么立刻可以斷定那么立刻可以斷定 p0 p1 pj-2 si-j+1 si-j+2 si-1 (樸素匹配的樸素匹配的)下一趟一定不匹配，可以跳過去下一趟一定不匹配，可以跳過去模式右滑模式右滑j-k位位模式右滑j

28、-k位 si-j si-j+1 si-j+2 si-k si-k+1 si-1 si p0 p1 p2 pj-k pj-k+1 pj-1 pj p0 p1 pk-1 pk3.4.2 字符串的特征向量字符串的特征向量Nn設模板設模板P由由m個字符組成：個字符組成： 記為記為P = q0 q1q2q3qm-1n令令特征向量特征向量N用于表示模板用于表示模板P的的字符分布特征，并簡稱字符分布特征，并簡稱N向量向量。它和它和P同長，由同長，由m個特征數(shù)個特征數(shù)n0 nm-1非負整數(shù)組成：非負整數(shù)組成： 記為記為N n0 n1n2n3nm-1 3.4.2 字符串的特征向量字符串的特征向量N(續(xù)續(xù))n下面

29、說明下面說明ni的含義和它的遞歸定的含義和它的遞歸定義：義： 列出模板列出模板P開頭的任意開頭的任意t個字符，個字符，把它稱為把它稱為P的前綴子串。的前綴子串。 q0q1q2qt-1 3.4.2 字符串的特征向量字符串的特征向量N(續(xù)續(xù)) 在在P的第的第i位置的左邊，也位置的左邊，也取出取出t個字符，稱為個字符，稱為i位置的位置的左子串左子串。 qi-t+1.qi-2qi-1qi3.4.2 字符串的特征向量字符串的特征向量N(續(xù)續(xù))n計算特征數(shù)計算特征數(shù)nin設法求出最長的設法求出最長的t最大的能最大的能夠與前綴子串匹配的左子串簡夠與前綴子串匹配的左子串簡稱第稱第i位的最長前綴串。位的最長前綴

30、串。nt就是要求的特征數(shù)就是要求的特征數(shù)ni。3.4.2 字符串的特征向量字符串的特征向量N(續(xù)續(xù))n特征數(shù)特征數(shù)ni ( 0 ni i )是遞歸定義的，定義如是遞歸定義的，定義如下：下：n n00，n 對于對于i 1的的ni ，假定前一位置的特征數(shù)，假定前一位置的特征數(shù)ni-1 ，并且，并且ni-1 k ；n 如果如果qi qk ，那么，那么ni k1 ；n 當當qi qk 且且 k0時，時，n 那么那么 令令k n k -1 ;n 讓讓循環(huán)直到條件不滿足；循環(huán)直到條件不滿足；n 當當qi qk 且且 k 0時，那么時，那么 ni 0;3.4.2 字符串的特征向量字符串的特征向量N(續(xù)續(xù))n

31、舉例：舉例：3.4.2 字符串的特征向量字符串的特征向量N(續(xù)續(xù))3.4.2 字符串的特征向量字符串的特征向量N(續(xù)續(xù))n【算法【算法3-14 】計算向量】計算向量Nnint *Next(String P)nn int m = (); /m為模板為模板P的長度的長度n assert( m 0); /假設假設m0，退出，退出n int *N = new intm; / 動態(tài)存儲區(qū)開辟整數(shù)數(shù)動態(tài)存儲區(qū)開辟整數(shù)數(shù)組組n assert( N != 0); /假設開辟存儲區(qū)域失敗，退出假設開辟存儲區(qū)域失敗，退出n N0 = 0;n for( int i =1 ; i 0 & Pi != Pk ) k =

32、 Nk-1; /根據(jù)根據(jù)Pi比較第比較第k位置前綴字符，決定位置前綴字符，決定Ni if(Pi = Pk) Ni = k+1; else Ni = 0 ; return N;3.4.3 KMP模式匹配算法模式匹配算法【算法【算法3-15 】KMP模式匹配算法模式匹配算法int KMP_FindPat(String S, String P, int *N, int startindex) /假定事先已經(jīng)計算出假定事先已經(jīng)計算出P的特征數(shù)組的特征數(shù)組N，作為輸入?yún)?shù)，作為輸入?yún)?shù) / S末尾再倒數(shù)一個模板長度位置末尾再倒數(shù)一個模板長度位置 int LastIndex = S.size - P.si

33、ze; if (LastIndex - startindex) 0) return (-1); /startindex過大，匹配無法成功過大，匹配無法成功 int i; / i 是指向是指向S內(nèi)部字符的游標，內(nèi)部字符的游標， int j = 0; / j 是指向是指向P內(nèi)部字符的游標，內(nèi)部字符的游標，3.4.3 KMP模式匹配算法模式匹配算法(續(xù)續(xù)) / S游標游標i循環(huán)加循環(huán)加1 for (i = startindex; i 0) j = Nj-1; /Pj與與Si相同，繼續(xù)下一步循環(huán)相同，繼續(xù)下一步循環(huán) if (P.strj = S.stri) j+; /匹配成功，返回該匹配成功，返回該S

34、子串的開始位置子串的開始位置 if( j = P.size) return (i - j +1); ; return (-1); /P和和S整個匹配失敗，函數(shù)返回值為負整個匹配失敗，函數(shù)返回值為負討論：如果討論：如果“i LastIndex，那么后面的就匹配不到。那么后面的就匹配不到。例如，例如，aaaaaaaaaab aaaaaab S.size=11，P.size=7，LastIndex = 4;“i = 4，j = 0, 匹配匹配a，接著，接著， “i = 5，j = 1就進行不了。就進行不了。KMP模式匹配例如一模式匹配例如一 0 1 2 3 4 5 6 P = a b a b a b b N =0 0 1 2 3 4 0 0 1 2 3 4 5 6 7 8 9 10 11 12S= a b a b a b a b a b a b b a b a b a b b X i=6,j=6, Nj-1=4 a b a b a b b X i=8, j=6, Nj-1 =4 a b a b a b b X i=10, j=6, j=4 a b a b a b b 0 1 2 3 4 5 6 7 8 9P = a a a a b a a a a cN =0 1 2 3 0 1