1?串的基本概念

1.1?串的定義

串：( string)(或字符串)是由零個或多個字符組成的有限序列，一般記為s='...'，其中，s是串的名，用單引號括起來的字符序列是串的值；(1<i≤n)可以是字母、數字或其他字符；串中字符的數目n稱為串的長度。零個字符的串稱為空串(null string)，它的長度為零。

子串：串中任意個連續的字符組成的子序列稱為該串的子串。包含子串的串相應地稱為主串。通常稱字符在序列中的序號為該字符在串中的位置。子串在主串中的位置則以子串的第一個字符在主串中的位置來表示。

說明∶串通常用一個字符數組來表示。從這個角度來講，數組 str內存儲的字特為'a'、'b'、'e'、 'd'、'e'、'f'、"\0'，其中"\0'作為編譯器識別串結來的標記。而串內字符為'a'、'b'、'c'、'd'、'e'、 'r'。因此數組 str的長度為7，而串 str的長度為6。

稱兩個串是相等的,當且僅當這兩個串的值相等。也就是說,只有當兩個串的長度相等,并且各個對應位置的字符都相等時才相等。比如'Nan?Chang'與'NanChang'就不是兩個相等的串，前者中間還有空格。

在各種應用中,空格常常是串的字符集合中的一個元素,因而可以出現在其他字符中間。由--個或多個空格組成的串′‘稱為空格串(blank string,請注意;此處不是空串)。它的長度為串中空格字符的個數。為了清楚起見,以后我們用符號“"來表示“空串”。

1.2?串的存儲結構

串的邏輯結構和線性表極為相似,區別僅在于串的數據對象約束為字符集。然而,串的基本操作和線性表有很大差別。在線性表的基本操作中,大多以“單個元素”作為操作對象,例如在線性表中查找某個元素、求取某個元素、在某個位置上插入一個元素和刪除一個元素等;而在串的基本操作中,通常以“串的整體”作為操作對象,例如在串中查找某個子串、求取一個子串、在串的某個位置上插人一個子串以及刪除一個子串等。

1.2.1?定長順序存儲表示

類似于線性表的順序結構存儲，用一組地址連續的存儲單元存儲串值的字符序列。在串定長順序存儲結構中，為每個串變量分配一個固定長度的存儲區，即定長數組。

#define?MAXSIZE?100? ? //字符串最長大小 typdef?struct{char?ch[MAXSIEZ];? ? //每個字符存儲int?length;? ? ? ? //串的實際長度 }SString;

注意∶不同的參考書對于串的結構體定義有所不同。有的用'\0'作為結束標記;有的不用'\0'，而用 額外定義的length 變量來表示事長以及標記串的結束。本文的定義是，給串尾加上"\0'結柬標記，同時 也設定 length，這樣做雖然多用了一個單位的存儲空間，但這是代碼中用起來最方便的形式。

1.2.2 變長分配存儲表示

變長分配存儲表示（又叫動態分配存儲表示）方法的特點是，在程序執行過程中根據需要動態分配。 其結構體定義如下∶

typedef?struct{char?*ch;? ? //指向動態分配存儲區首地址的字符指針int?length;? ? //長度 }Str;

變長分配頁稱為堆分配，在C語言中，存在一個稱之為“堆”的自t存儲區，并川 malloc ()和 free ( ) 函數來完成動態存儲管理。利用malloc ()為每個浙產生的串分配一塊實際串長所需的存儲空間，若分配成功，則返回一個指向起始地址的指針，作為串的基地址，這個串由 ch 指針來指示:若分配失敗.則返畫NULL。己分配的空間可用f ee ()釋放掉。

1.2.3?塊鏈存儲表示

類似于線性表的鏈式存儲結構，也可采用鏈表方式存儲串值。由于串的特殊性（每個元素只有一個字符)，在具體實現時，每個結點既可以存放一個字符，也可以存放多個字符。每個結點稱為塊，整個鏈長稱為塊鏈結構。圖(a)是結點大小為4(即每個結點存放4個字符）的鏈表，最后一個結點古不滿時通常用“#”補上：圖(b)是結點大小為1的鏈表。

2?串的基本操作

對于串的基本操作集可以有不同的定義方法,讀者在使用高級程序設計語言中的串類型時,應以該語言的參考手冊為準。在上述抽象數據類型定義的13種操作中,串賦值StrAssign,串比較StrCompare,求串長StrLength、串聯接Concat以及求子串SubString5種操作構成串類型的最小操作子集。即這些操作不可能利用其他串操作來實現,反之.其他串操作(除串清除ClearString和串銷毀DestroyString外)均可在這個最小操作子集上實現。

（1）串賦值StrAssign（）

與普通變量賦值操作不同，串的賦值操作不能直接用"="來實現。因為串是一個數組，如果將一個數組的值賦給另一個數組，則直接用"="是不可行的，必須對數組中的每個元素進行逐一賦值操作。串賦值操作函數 strassign（）具體實現的代碼如下所示，其功能是將一個常量字符串賦值給 str，賦值操作成功返回1.否則返回0。

int Btrasslgn(Str& str,char* ch){if(str.ch)free(str.ch); //釋放原串空間int len=0;char *c=ch;whfle(*c){ //求ch 串的長度++len;=+c;}if(len==0){ //如果 ch為空串，則直接返回空串str.ch=NULL;str.length=0:return 1;}else{str.ch=(char*)malloc(sizeof(char)*(len+1));//取len+1是為了多分配一個空間存放"\0"字符? ? if(str.ch==NULL)return?0;else{c=ch;for(int?i=0;i<=len;++i,++c){str.ch[i]=*c; /*注意∶循環條件中之所以用"<="，是為了將ch最后的'\0'復制到新串中作為結束標記*/str.length=len;return?1;}} }

數 strassign（）使用時格式如下∶

strassign(str,"apple?banana")

（2）取串長操作strlength（）

int?strlength(Str?str){return?str.length; }

如果在沒有給出串長度信息的情況下，求串長度的操作可以借鑒函數 strassign（）中的求輸入串長度部分的代碼來實現，也是非常簡單的。

（3）串比較操作strcompare（）

串的比較操作是串排序應用中的核心操作。例如，在單詞的字典排序中，需要通過患比較操作來確定一個單詞在字典中的位置，規則如下∶設兩串 A和B中的待比較字符分別為a和b，如果a的ASCII 碼小于b的 ASCII碼，則返回A小于B標記;如果a的ASCII碼大于b的 ASCII碼，則返回A大于B 標記;如果a的 ASCII碼等于b的 ASCII碼，則按照之前的規則繼續比較兩串中的下一對字符。經過上述步驟，在沒有比較出A 和B 大小的情況下，先結束的串為較小串，兩串同時結束則返回兩串相等標記。

int?strcompare(Str?s1,Str?s2){for(int?i=0;i<s1.length;i++){if(s1.ch[i]!=s2.ch[i])return?s1.ch[i]-s2.ch[i];return?s1.length-s2.length; }

（4）串連接操作

將兩個串首尾相接，合并成一個字符串的操作稱為串連接操作。

int?concat(Str?&str,Str?str1,Str?str2){if(str.ch){free(str.ch)str,ch=NULL;}str.ch=(char*)malloc(sizeof(char)*(str1.length+str2.length));if(str.ch==NULL)return?0;int?i=0;while(i<str1.length){str.ch[i]==str.ch[i];i++;}int?j=0;while(j<=str2.length){//注意，之所以用"<="是為了連同str2.ch最后的'\0'一起復制str,ch[i+j]=str2.ch[j];j++;}str.length=str1.length+str2.length;return?1; }

（5）求子串操作?substring()

求從給定串中某一位置開始到某一位置結束的串的操作稱為求子串操作（規定開始位置總在結束位置前面），如下面的代碼實現了求 str 串中從pos 位置開始，長度為len 的子串，子串由 substr返回給用戶。

int?substring(Str&?substr,Str?str,int?pos,int?len){if(pos<0||pos>=str,length||len<0||str>str.length-pos)return?0;if(substr.ch){free(substr.ch);substr.ch=NULL;}if(len==0){substr.ch=NULL;substr.length=0;return?1;}else{substr.ch=(char*)malloc(sizeof(char)*(len+1));int?i=pos;int?j=0;while(i<pos+len){subsr.ch[j]=str.ch[i];i++;j++;}substr.ch[j]='\0';subtstr.length=len;return?1;} }

（6）串清除操作

int?clearstring(Str?&str){if(str.ch){free(str.ch);str.ch=NULL;}str.length=0;return?1; }

3?串的相關應用

3.1?求子串位置的定位

子串的定位操作通常稱做串的模式匹配(其中T稱為模式串),是各種串處理系統中最重要的操作之一。采用定長順序存儲結構,可以寫出不依賴于其他串操作的匹配算法,如下列算法所示。

算法主要思想：在Index函數過程中,分別利用計數指針i和j指示主串S和模式串T中當前正待比較的字符位置。算法的基本思想是:從主串S的第pos個字符起和模式的第一個字符比較之,若相等,則繼續逐個比較后續字符﹔否則從主串的下一個字符起再重新和模式的字符比較之。依次類推,直至模式T中的每個字符依次和主串S中的一個連續的字符序列相等,則稱匹配成功,函數值為和模式T中第一個字符相等的字符在主串S中的序號,否則稱匹配不成功,函數值為零。下圖展示了模式T='abcac'和主串S的匹配過程(pos=1)。

主串"ABABCABCACBAB"和模式串"ABCAC"的6趟匹配過程，紅色標出了當前匹配失敗的位置。

實現代碼如下：

int?Index(SString?S,SString?T,int?pos){ //返回子串T在主串s中第pos個字符之后的位置。若不存在,則函數值為0。 //其中,T非空,1≤pos≤StrLength(S)。i=pos;? ? j=1;while(i<=S[0]&&j<=T[0]{if(S[i]==T[j]){i++;j++;}}if(j>T[0])? ? return?i-T[0];else?return?0; }

最壞時間復雜度：O(nm)，n,m分別為主串和模式串長度。

例如，當模式串為0000001'，而主串'0000000000000000000000000000000000000000000001'，由于模式中前6個字符均為“0"”，主串中前45個字符均為“0”，每趟[匹配都是比較到模式的最后一個字符時才發現不等，指針i需回溯40 次、總比較次數為40x7=280 次。

3.2?串的模式匹配算法——KMP

3.2.1?字符串的前綴、后綴和部分匹配值

要了解子串的結構，首先要弄清楚幾個概念:前綴、后綴和部分匹配值。前綴指除最后一個字符以外，字符串的所有頭部子串:后綴指除第一個字符外，字符串的所有尾部子串:部分匹配值則為字符串的前綴和后綴的最長相等前后綴長度。下面以'ababa '為例進行說明:

• 'a'的前綴和后綴都為空集，最長相等前后綴長度為0。

• 'ab'的前綴為{a}，后綴為{b}，{a}∩{b}=?，最長相等前后綴長度為0。

• 'aba'的前綴為{a,ab}，后綴為{a,ba}，{a,ab}∩{a,ba}={a}，最長相等前后綴長度為1。

• 'abab'的前綴為{a,ab,aba}，后綴為{b,ab,bab}，{a,ab,aba}∩{b,ab,bab}={ab}，最長相等前后綴長度為2。

• 'ababa'的前綴為{a,ab,aba,abab}，后綴為{a,ba,aba,baba}，{a,ab,aba,abab}∩{a,ba,aba,baba}={a,aba}，最長相等前后綴長度為3。

所以字符串'ababa'的部分匹配值為00123。

3.2.2?Next數組求法

由于上述3.1所采用的暴力求解方法，有一些不必要的遍歷過程可以進行舍去，就比如第二趟中，在第一趟就已經知道了第二趟開頭是B，于是我們就可以嘗試著。所以可以用一個數組在遍歷之前就進行存儲相關移動的數據，也就是Next數組。（詳細可以去看嚴蔚敏，吳偉民. 數據結構[M]. 北京：清華大學出版社.書中介紹）

next數組的求解方法：首先第一位的next值直接給0，第二位的next值直接給1，后面求解每一位的next值時，都要前一位進行比較。首先將前一位與其next值的對應位進行比較，若相等，則該位的next值就是前一位的next值加上1；若不等，繼續重復這個過程，直到找到相等某一位，將其next值加1即可，如果找到第一位都沒有找到，那么該位的next值即為1。

步驟如下：

（1）前兩位固定為0，1

手動計算方法：前兩位固定0，1不變

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1

（2）計算第三位的時候，看第二位b的next值為1，則把b和1對應的a進行比較，不同，則第三位a的next的值為1，因為一直比到最前一位，都沒有發生比較相同的現象。

手動計算方法：看前兩位字符的最大公共前后綴長度，ab最大公共前后綴長度位0，所以第三位Next數值為0+1=1

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1

（3）計算第四位的時候，看第三位a的next值為1，則把a和1對應的a進行比較，相同則第四位a的next的值為第三位a的next值加上1為2。因為是在第三位實現了其next值對應的值與第三位的值相同。

手動計算方法：看前三位字符的最大公共前后綴長度，aba最大公共前后綴長度位1，公共前后綴為a，所以第四位Next數值為1+1=1

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2

（4）計算第五位的時候，看第四位a的next值為2，則把a和2對應的b進行比較，不同則再將b對應的next值1對應的a與第四位的a進行比較，相同則第五位的next值為第二位b的next值加上1為2。因為是在第二位實現了其next值對應的值與第四位的值相同。

手動計算方法：看前四位字符的最大公共前后綴長度，abaa最大公共前后綴長度位1，公共前后綴為a，所以第五位Next數值為1+1=1

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2

（5）計算第六位的時候，看第五位b的next值為2，則把b和2對應的b進行比較，相同則第六位c的next值為第五位b的next值加上1為3，因為是在第五位實現了其next值對應的值與第五位相同。

手動計算方法：看前五位字符的最大公共前后綴長度，abaab最大公共前后綴長度位2，公共前后綴為ab，所以第四位Next數值為2+1=3

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2	3

代碼實現：

void?get_next(String?T,int?next[]){int?i=1,j=0;next[i]=0;while(i<T.length){if(j==0||T.ch[i]==T.ch[i]{i++,j++;next[i]=j;? ? ? ? //若pi=pj，則next[j+i]=next[j]+1;}elsej=next[j];? ? ? ? //否則令j=next[j]，循環繼續} }

運用next數組構建的模式匹配算法KMP

int?Index_KMP(String?S,String?T,int?next[]){int?i=1,j=1;while(i<=S.length&&j<=T.length[j]){if(j==0||S.ch]i]==T.ch[j]){i++,j++;? ? ? ? ? ? ? ? //繼續比較后面字符}elsej=next[j];? ? ? ? ? ? ? ? //模式串向后移動}if(j>T.length)return?i-T.length;? ? ? ? ? ? //匹配成功elsereturn?0;

時間復雜度：O(m+n)，n,m分別為主串和模式串長度。

盡管普通模式匹配的時間復雜度是O(mn)，KMP算法的時間復雜度是O(m+n)，但在一般情況下，普通模式匹配的實際執行時間近似為O(m + n)，因此至今仍被采用。KMP算法僅在主串與子串有很多“部分匹配”時才顯得比普通算法快得多，其主要優點是主串不回溯。

3.2.3 NextVal數組求法

求解nextval數組是基于next數組的，模式串每一個位置的字符和其next數組值給出的下標的對應位置的數作比較，相等就取nextval中對應的next數組值作為當前位置字符的nextval值，不等就直接取當前位置字符的next數組的值作為nextval的值。

（1）next-val數組第一個數直接為0。

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2	3
nextval數組	0

（2）next-val第二數：模式串第二個字符為b，對應的下標數組第二個數是1，那就是將模式串的第1個字符和b相比較，a!=b,所以直接將下標數組第二個數1作為nextval數組第二個數的值1

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2	3
nextval數組	0	1

（3）第三個數：模式串第三個字符為a，對應下標數組第三個數為1，取其作為下標，找到模式串第1個字符為a，a=a，那取next-val的第一個數做為nextval第三個數的值，也就是0

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2	3
nextval數組	0	1	0

（4）第四個數：模式串第四個字符為a，對應下標數組第四個數為2，取其作為下標，找到模式串第2個字符為b，a!=b，所以直接將下標數組第四個數2作為nextval數組第二個數的值2

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2	3
nextval數組	0	1	0	2

（5）第五個數：模式串第五個字符為b，對應下標數組第三個數為2，取其作為下標，找到模式串第2個字符為b，b=b，那取nextval的第二個數做為nextval第五個數的值，也就是1

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2	3
nextval數組	0	1	0	2	1

（6）第六個數：模式串第六個字符為c，對應下標數組第六個數為3，取其作為下標，找到模式串第3個字符為a，c!=a，所以直接將下標數組第六個數3作為nextval數組第二個數的值3

序號	1	2	3	4	5	6
模式串	a	b	a	a	b	c
next數組	0	1	1	2	2	3
nextval數組	0	1	0	2	1	3

nextval代碼求解：

void?get_nextval(String?T,int?nextval[]){int?i=1,j=0;nextval[1]=0;while(i<T.length){if(j==0||T.ch[i]==T.ch[j]){i++,j++;if(T.ch[i]!=T.ch[j])? ? //如果前面字符與當前字符相等，則nextval值為前面字符的nextval值nextval[i]=j;elsenextval[i]=nextval[j];//不等就直接是當前的next數值的值}elsej=nextval[j];} }

下面是實驗平臺模擬出來的結果：

3.2.4?next數組與nextval數組對比

next數組的缺陷舉例如下：比如主串是"aabXXXXXXXXXXXXXX"，模式串"aac"。通過計算 "aac" 的next數組為012，當模式串在字符c上失配時，會跳到第2個字符，然后再和主串當前失配的字符重新比較，即此處用模式串的第二個a和主串的b比較，即 "aabXXXXXXXXXXXXXX"vs"aac"，顯然a也不等于b。然后會跳到1接著比，直到匹配成功或者匹配失敗主串后移一位。而"aac"的nextval數組為002 當在c失配時會跳到2，若還失配就直接跳到0，比next數組少比較了1次。在如果模式串很長的話，那可以省去很多比較，因此使用nextval數組比next數組高效。

3.3?字符串哈希

算法問題：

每個女孩都喜歡購物，蒲公英也是。現在，她發現這家店每天都在漲價，因為春節快到了。她很喜歡一家叫“memory”的店。現在她想知道這個商店的價格在每天變化后的排名。

輸入：一行包含一個數字n (n<=10000)，代表商店的數量。然后是n行，每行包含一個字符串(長度小于31，且只包含小寫字母和大寫字母)，表示商店的名稱。然后一行包含一個數字m (1<=m<=50)，代表天數。然后m部分，每個部分包含n行，每一行包含一個數字s和一個字符串p，代表這一天，商店p的價格增加了s。

輸出包含m行，在第i行打印商店“memory”的第i天后的排名的數字。我們將排名定義為:如果有t個商店的價格高于“memory”，那么它的排名為t+1。

算法思想：

（1）把字符串改成數字的形式存儲起來，也就是把字符串的ASSIC值進行轉化，然后再用這個ASSIC值將其轉化成其他進制，進制轉化也有特定的要求，需轉化成13，31，1331，13331?......等進制，因為有學者統計過，用這些進制轉化之后，哈希沖突遠比其他進制轉化小。

（2）解決哈希沖突，有三種方法，第一就是上述所講的進制轉化數字的選取；第二就是在發生沖突時候，尋找其他空閑位置進行存儲；第三就是再哈希法，創建另外一個哈希轉化進行存儲。

實現代碼：

#include<bits/stdc++.h> using namespace std; const int N = 10005; struct node{char name[35];int price; };vector<node>List[N]; // 用來解決沖突 unsigned int BKDRHash(char*str){ // 哈希函數 unsigned int seed = 31,key = 0;while(*str)key = key * seed + (*str++);return key & 0x7fffffff; }int main() {int n,m,key,add,memory_price,rank,len;int p[N];char s[35];node t;while(cin >> n){for(int i = 0; i < N;i++)List[i].clear();for(int i = 0; i < n; i++){cin >> t.name;key = BKDRHash(t.name) % N; //計算hash值并取余 List[key].push_back(t); //hash值可能沖突，把沖突的哈希值都存起來 }cin >> m;while(m--){rank = len = 0;for(int i = 0; i < n; i++){cin >> add >> s;key = BKDRHash(s) % N; //計算哈希值 for(int j = 0; j < List[key].size();j++){ //沖突問題處理 if(strcmp(List[key][j].name,s) == 0){List[key][j].price += add;if(strcmp(s,"memory") == 0){memory_price = List[key][j].price;}else{p[len++] = List[key][j].price;}break;}}}for(int i = 0; i < len; i++){if(memory_price < p[i])rank++;}cout << rank + 1 << endl;}}return 0; } 輸入： 3 memory kfc wind 2 49 memory 49 kfc 48 wind 80 kfc 85 wind 83 memory輸出： 1 2

3.4?最長公共前綴

算法問題：編寫一個函數來查找字符串數組中的最長公共前綴。如果不存在公共前綴，返回空字符串 ""。

示例 1:

輸入: ["flower","flow","flight"]

輸出: "fl"

示例 2:

輸入: ["dog","racecar","car"]

輸出: ""

算法思想：

（1）當字符串數組長度為 0 時則公共前綴為空，直接返回

（2）令最長公共前綴 cp 的值為第一個字符串，進行初始化

（3）遍歷后面的字符串，依次將其與 cp 進行比較，兩兩找出公共前綴，最終結果即為最長公共前綴

（4）如果查找過程中出現了 cp為空的情況，則公共前綴不存在直接返回

char * longestCommonPrefix(char ** strs, int strsSize){ int i,j,k;char *cp = NULL ;//char *cp1="";if(!strsSize) //空數組情況return "";for(j=0; *(*strs+j) != '\0'; j++){for(i=1; i<strsSize ;i++){ if( *(*(strs+i)+j) != *(*strs+j) ){if(j==0)return "";else{ cp = (char *)malloc(sizeof(char)*(j+1));for(k=0;k<j;k++){ cp[k]=*(*strs+k);}cp[k]='\0';return cp;}}}}cp = (char *)malloc(sizeof(char)*(j+1));for(k=0;k<j;k++){cp[k]=*(*strs+k);}cp[k]='\0';return cp; }

下面是實驗平臺運行結果：

3.5 最長公共子序列LCS

所謂的最長公共子序列，就說在兩個字符串str1='ABCBDAB'，str2='BDCABA'，紅色部分 'BCBA' 就是兩個字符串的最長公共子序列。在這里，公共子序列的字符之間可以不是連續，所以公共最長子序列不唯一。

字符子串指的是字符串中連續的n個字符，如abcdefg中，ab，cde，fg等都屬于它的字串。

字符子序列指的是字符串中不一定連續但先后順序一致的n個字符，即可以去掉字符串中的部分字符，但不可改變其前后順序。如abcdefg中，acdg，bdf屬于它的子序列，而bac，dbfg則不是，因為它們與字符串的字符順序不一致。

3.5.1?最長公共子數列長度

算法思想：采用動態規劃的思想，先設一個二維數組，行代表字符串str1，列代表字符串str2。第一列和第一行都設置為0。0代表該行字符與列字符不相同。如果在行列字符比較不相同的時候，取上方數字作為當前數字；如果行、列相同，則從左上角數字加1。

代碼實現：

#include <cmath> #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm>using namespace std;char a[1001], b[1001]; int dp[1001][1001], len1, len2;void lcs(int i,int j) {for(i=1; i<=len1; i++){for(j=1; j<=len2; j++){if(a[i-1] == b[j-1])dp[i][j] = dp[i-1][j-1] + 1;else if(dp[i-1][j] > dp[i][j-1])dp[i][j] = dp[i-1][j];elsedp[i][j] = dp[i][j-1];}} }int main() {while(~scanf(" %s",a)){scanf(" %s", b);memset(dp, 0, sizeof(dp));len1 = strlen(a);len2 = strlen(b);lcs(len1, len2);printf("%d\n", dp[len1][len2]);}return 0; }

時間復雜度：O(n*m)，n,m為兩個字符串長度。

3.5.2 最長公共子數列

算法思想：通過上述最長子序列長度生成的二維數組，然后逆著找到最長子序列。如果左邊、左上角、上面三個數字都比該數字小，則該數字是有左上角加1得到的；如果與左邊數字相等，上方也相等則是由上方數字得到；如果與左上角數字大，而且左邊數字等于該數字，則是由左邊得到的；依次類推找到邊上為止。

代碼實現：

#include <iostream> #include <cstring> using namespace std; const int N = 10; int c[N][N], b[N][N]; char s1[N], s2[N]; int len1, len2; void LCS() {for (int i = 1; i <= len1; i++) {for (int j = 1; j <= len2; j++) {if (s1[i - 1] == s2[j - 1]) { //注：此處的s1與s2序列是從s1[0]與s2[0]開始的c[i][j] = c[i - 1][j - 1] + 1;b[i][j] = 1;}else {if (c[i][j - 1] >= c[i - 1][j]) {c[i][j] = c[i][j - 1];b[i][j] = 2;}else {c[i][j] = c[i - 1][j];b[i][j] = 3;}}}} }void LCS_PRINT(int i, int j) {if (i == 0 || j == 0) {return;}if (b[i][j] == 1) {LCS_PRINT(i - 1, j - 1);cout << s1[i - 1];}else if (b[i][j] == 2) {LCS_PRINT(i, j - 1);}else {LCS_PRINT(i - 1, j);} }int main() {cout << "請輸入X字符串" << endl;cin >> s1;cout << "請輸入Y字符串" << endl;cin >> s2;len1 = strlen(s1);len2 = strlen(s2);for (int i = 0; i <= len1; i++) {c[i][0] = 0;}for (int j = 0; j <= len2; j++) {c[0][j] = 0;}LCS();cout << "s1與s2的最長公共子序列的長度是：" << c[len1][len2] << endl;cout << "s1與s2的最長公共子序列是：";LCS_PRINT(len1, len2);return 0; }

下列是實驗平臺運行結果：

4?總結

在學習串這個章節時候，需要讀者深入了解串的特性，因為串在許多算法中運用極為廣泛。無論是最長前綴后綴子序列，還是KMP算法，或者是字典樹，都是十分重要的知識，也是比較難掌握的知識，由于本文篇幅有限，有許多算法未能全部講完，所以也需要讀者自己去了解并掌握。

參考文獻：

[1] 蘇小紅，孫志剛，陳惠鵬等編著. C語言大學實用教程（第四版）[M]. 北京：電子工業出版社，2017.

[2] 嚴蔚敏，吳偉民. 數據結構[M]. 北京：清華大學出版社.

[3]?羅勇君，?郭衛斌.算法競賽_入門到進階[M].北京：清華大學出版社.

作者：

江西師范大學_姜嘉鑫；???江西師范大學_龔俊

總結

以上是生活随笔為你收集整理的串的详细讲解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。