2.4 字符串的實際應用
2.4.1 字符串包含問題
1）串的模式匹配算法
例1：在字符串中查找子串。給定一個字符串A，要求在A中查找一個子串B。
如主串A=“ababcabcacbab”，要你在A中查找子串（模式串）B=“abcac”。
解答：
（1）使用最基礎的算法（BF算法），代碼如下：
char＊ strFind(const char ＊string, const char ＊substring){
assert(string!=NULL&& substring!=NULL);
int m=strlen(string);
int n=strlen(substring);
if(m < n)
return NULL;
for (int i=0; i<=m-n; i++){ //時間復雜度為O((m-n+1)＊n)
for (int j=0; j<n; j++){
if (string[i+j]!=substring[j])
break;
}
if (j == n)
return string+i;
}
return NULL;
}
（2）或者使用KMP算法，此時復雜度為O(m+n)。
KMP算法的比較過程是：
第一趟匹配：
第二趟匹配：
直接拿模式串的第1位與主串的第3位（此位上一趟匹配失敗）做比較。
第三趟匹配：
直接拿模式串的第2位與主串的第7位（此位上一趟匹配失敗）做比較。注意模式串的第一位沒有參與比較，這是因為KMP算法已經推得此位必然相等。
第三趟查找模式串成功。
可見KMP算法每當一趟匹配過程中出現字符比較不等時，不需回溯主串，而是利用已經得到的“部分匹配”結果將模式串向右“滑動”盡可能遠的一段距離后，繼續進行比較，且此時并不一定是拿模式串的第一位繼續比較。
下面給出kmp算法的代碼，kmp算法的原理及next數組的求法請參考《數據結構》或者《算法導論》等書籍。
int kmp_search(const char ＊ src, int slen, const char ＊ patn, int plen, const
int ＊ nextval, int pos){
int i=pos, j=0;
while (i < slen && j < plen){
if(j == -1 || src[i] == patn[j]){++i;++j;}
else{
j=nextval[j]; /＊當匹配失敗時直接用p[j_next]與s[i]比較＊/
}
}
if(j >= plen)
return i-plen;
else
return -1;
}
下面給出計算next數組的函數。
void get_nextval(char const＊ ptrn, int plen, int＊ nextval){
int i=0;nextval[i]=-1; int j=-1;
while(i < plen-1){
if(j == -1 || ptrn[i] == ptrn[j]){++i;++j;nextval[i]=j;}
else
j=nextval[j];
}
}
下列函數為改進了的計算next數組的函數。
void get_nextval(char const＊ ptrn, int plen, int＊ nextval){
int i=0;nextval[i]=-1; int j=-1;
while(i < plen-1){
if(j == -1 || ptrn[i] == ptrn[j]){
++i;
++j;
if(ptrn[i] != ptrn[j])
nextval[i]=j;
else
nextval[i]=nextval[j];
}
else
j=nextval[j];
}
}
例2：在長度為M的字符串中，查找長度為N的字符串的最好時間復雜度是 ？（2012·網易）
解答：O(M+N)。使用KMP算法。
2）字符串移位包含問題
例1：給定兩個字符串s1和s2，要求判定s2是否能夠被s1做循環移位得到的字符串包含。例如，給定s1=AABCD和s2=CDAA，返回true；給定s1=ABCD和s2=ACBD，返回false。
解答：
1）以s1=ABCD為例，先分析對s1進行循環移位之后的結果，如下所示：
ABCD->BCDA->CDAB->DABC->ABCD……
假設我們將前面移走的字符串保留下來，則有：
ABCD->ABCDA->ABCDAB->ABCDABC->ABCDABCD
這里，我們可以發現，實際對s1的循環移位得到的字符串實際為s1s1的子字符串。那么我們判斷s2是否可以通過s1循環移位得到包含，則只需要判斷s1s1中是否含有s2即可，上節中已經給出了這種解法的答案，其中包括使用KMP算法。
其他同類問題：假設有一個函數isSubstring，其功能是判斷一個字符串是不是另外一個字符串的子串。現在給你兩個字符串s1與s2，請僅使用isSubstring函數判斷s2是否能夠被s1做循環移位得到的字符串包含。
解答思想是：
如果字符串s1的長度小于s2的長度，則返回0；
否則，連接s1與其自身得到新字符串s1s1，然后判斷s2是否是s1s1的子串，若是返回1，若不是返回0。
2）事實上，對于移位包含問題完全可以像普通包含問題一樣解決，只不過在指針指向s1末尾元素時，下一操作重新回到s1頭元素，這可通過求模操作解決，代碼如下：
bool find(const char＊ const src, const char＊ const des){
assert(src!=NULL&&des!=NULL);
int lenSrc=strlen(src);
int lenDes=strlen(des);
if(lenSrc < lenDes)
return false;
int k;
for(int i=0;i<lenSrc;++i){
k=i;
for(int j=0;j<lenDes;j++){
if(src[k++%lenSrc]!=des[j])
break;
}
if(k-i==lenDes)
return true;
}
return false;
}
2.4.2 字符串轉換為數字
例1：輸入一個表示整數的字符串，把該字符串轉換成整數并輸出。例如輸入字符串"345"，則輸出整數345。（2012·亞馬遜在線測試、劍指Offer例題）
解答：可以依次掃描字符串，每掃描到一個字符，我們把在之前得到的數字乘以10 再加上當前字符表示的數字。這個思路用循環不難實現。
但整數可能不僅僅只含有數字，還有可能以'+'或者'-'開頭，表示整數的正負。因此我們需要把這個字符串的第一個字符做特殊處理。如果第一個字符是'+'號，則不需要做任何操作；如果第一個字符是'-'號，則表明這個整數是個負數。
接著還要考慮非法輸入：
1）需要判斷這個指針是不是為空。
2）輸入的字符串中可能含有不是數字的字符。每當碰到非法的字符，轉換停止。
3）溢出問題。若溢出，則返回0。
參考代碼：
enum Status {kValid=0, kInvalid};
int g_nStatus=kValid;
int StrToInt(const char＊ str){
g_nStatus=kInvalid;
long long num=0;
if(str != NULL){
const char＊ digit=str;
bool minus=false;
if(＊digit == '+')
digit ++;
else if(＊digit =='-'){
digit ++;
minus=true;
}
while(＊digit != '\0'){
if(＊digit >= '0' && ＊digit <= '9'){
num=num ＊ 10+(＊digit - '0');
if(num > std::numeric_limits<int>::max()){
num=0;
break;
}
digit ++;
}
else{
num=0;
break;
}
}
if(＊digit == '\0'){
g_nStatus=kValid;
if(minus)
num=0- num;
}
}
return num;
}
例2：假設有一個各種字母組成的字符串s1，假設還有另外一個字符串s2，而且s2字符串里的字母數相對少一些。從算法上講，什么方法能最快地查出s2中的字母是否在s1中都有？（google面試題）
比如，如果是下面兩個字符串：
string 1: ABCCDEFGHLMNOPQRS
string 2: DCGSRQPOMC
答案是true，所有在string2里的字母string1也都有，且string2中C出現兩次，string1中C也出現了兩次。
如果是下面兩個字符串：
string 1: ABCCDEFGHLMNOPQRS
string 2: DCGSRQPOZC
答案是false，因為第二個字符串里的Z字母不在第一個字符串里。
解答：注意題意中，當短字符串字母有重復時，長字符串需滿足對應字符重復個數大于等于短字符串中相應字符出現的次數。
1）一個方案是先對這兩個字符串的字母進行排序，然后同時對兩個字串依次輪詢。兩個字串的排序需要(常規情況)O(m log m)+O(n log n)次操作，之后的線性掃描需要O(m+n)次操作。
2）對第一個字串進行輪詢，把其中的每個字母都放入一個hashtable里(時間復雜度是O(m)，hashtable可以利用數組實現)，字母（當作hashtable的key）每出現一次，則value加1；
然后輪詢第二個字串，在hashtable里查詢每個字母（key），看能否找到，找到后若其值大于0，則將對應值的value減1，如果找到某個key對應的value為0，說明沒有匹配成功，時間復雜度為O(n)。故總的算法時間復雜度為O(n+m)。
3）可以給每個字母分配一個素數，從2開始，以此類推。這樣A將會是2，B將會是3，C將會是5，等等。現在遍歷第一個字串，把每個字母代表的素數相乘。你最終會得到一個很大的整數。
然后，輪詢第二個字符串，用每個字母代表的素數除它。如果除的結果有余數，這說明有不匹配的字母。如果整個過程中沒有余數，你應該知道它是第一個字串恰好的子集了。此算法需要考慮一個問題，若第一個字符串較長，則最后的乘積可能會超出int的表示范圍。此時可以考慮采用大數乘法。
例3：輸入兩個很大的正數（用C字符串表示），輸出它們的乘積，假設不考慮非法輸入。
解答：
void multiply(const char ＊a, const char ＊b){
assert(a != NULL && b != NULL);
int i, j, ca, cb, ＊s;
ca=strlen(a);
cb=strlen(b);
s=(int ＊)malloc(sizeof(int)＊(ca+cb)); //分配存儲空間
for (i=0;i<ca+cb;i++)
s[i]=0; // 每個元素賦初值0
for (i=0;i<ca;i++)
for (j=0;j<cb;j++)
s[i+j+1]+=(a[i]-'0')＊(b[j]-'0');
for (i=ca+cb-1;i>=0;i--) // 這里實現進位操作
if (s[i]>=10){
s[i-1]+=s[i]/10;
s[i]%=10;
}
char ＊c=(char ＊)malloc((ca+cb)＊sizeof(char));
i=0;
while(s[i]==0) i++; // 跳過頭部0元素
for (j=0;i<ca+cb;i++, j++) c[j]=s[i]+'0';
c[j]='\0';
for (i=0;i<ca+cb;i++) cout<<c[i];
cout<<endl;
free(s);
free(c);
}
2.4.3 其他應用
例1：字符串中單詞的逆轉，即將單詞出現的順序進行逆轉。如將“Today is Friday!”逆轉為“Friday！is Today”。（2012·百度、人人）
分析：本題也可以作為循環移位來出題，即將“Today is Friday!”循環移7位。
解答：想要不使用額外的空間完成，可以分為兩部，首先將字符串全逆轉，這樣單詞出現的順序得到逆轉（“Today is Friday!”逆轉為“!yadirF si yadoT”）；然后通過空格分割單詞，單詞自身進行逆轉。
void Reverse(char ＊pb, char ＊pe){
if(pb == NULL || pe == NULL) return;
while(pb < pe){
char tmp=＊pb;//交換pb和pe的內容
＊pb=＊pe;
＊pe=tmp;
pb ++, pe --;
}
}
char＊ ReverseSentence(char ＊pData){
if(pData == NULL) return NULL;
char ＊pBegin=pData;char ＊pEnd=pData;
while(＊pEnd != '\0')
pEnd ++;
pEnd--;//去掉空格
Reverse(pBegin, pEnd);
pBegin=pEnd=pData;
while(＊pBegin != '\0'){
if(＊pBegin == ' '){
pBegin ++;
pEnd ++;
continue;
}
// 反轉單詞
else if(＊pEnd == ' ' || ＊pEnd == '\0'){
Reverse(pBegin, --pEnd);
pBegin=++pEnd;
}
else
pEnd ++;
}
return pData;
}
例2：刪除模式串中出現的字符，如“welcome to asted”，模式串為“aeiou”那么得到的字符串為“wlcm t std"，要求性能最優，字符串中全部為小寫字母。（2012·盛大）
解答：最簡單的方法是依次遍歷每個字符，如是模式串中的一員，則刪除。
void fun(char ＊ s){
assert(s != NULL);
int i=0, j=0;
while(s[j] != '\0'){
while(s[j] == 'a' || s[j] == 'e' || s[j] == 'i' || s[j] == 'o' || s[j] == 'u')
j++;
s[i++]=s[j++];
}
s[i]='\0';
}
也可以給每個字母分配一個素數，從2開始，以此類推。這樣a將會是2，b將會是3，c將會是5，等等，然后得出“aeiou”的乘積multi，現在遍歷字符串s，把每個字母代表的素數除multi，若能整除，則將其刪除。
例3：刪除字符串開始及末尾的空白符（若干空格），并且把數組中間的多個空格（如果有）符轉化為1個。（2012·人民搜索）
解答：
void fun(char ＊ s){
int i=0, j=0;
while(s[j] == ' ') //刪除頭部的空白符
j++;
int len=strlen(s)-1;
while(s[len] == ' ') len--;//刪除尾部的空白符
s[len+1]='\0';
while(s[j] != '\0'){
while(s[j] == ' ')
j++;
/＊將中間連續的空白符變為一個，判斷i!=0是為了防止將頭部的連續字符變為1個＊/
if(s[j-1] == ' ' && s[j-2] == ' '&&i!=0)
s[i++]=' ';
s[i++]=s[j++];
}
s[i]='\0';
}
例4：在一個字符串中找到第一個只出現一次的字符。如輸入abaccdeff，則輸出b，假設字符集是ASCII。
解答：由于ASCII字符是一個長度為8的數據類型總共有可能256種可能，每個字母根據其ASCII碼值作為數組的下標對應數組的對應項，而數組中存儲的是每個字符對應的次數。我們第一遍掃描這個數組時，每碰到一個字符，在哈希表中找到對應的項并把出現的次數增加一次。這樣在進行第二次掃描時，就能直接從哈希表中得到每個字符出現的次數了。
參考代碼如下：
void FirstNotRepeatingChar(const char＊ pString){
assert(pString != NULL);
const int tableSize=256;
unsigned int hashTable[tableSize];
for(unsigned int i=0; i < tableSize; ++ i)
hashTable[i]=0;
const char＊ pHashKey=pString;
while(＊(pHashKey) != '\0')
hashTable[＊(pHashKey++)] ++;
pHashKey=pString;
while(＊pHashKey != '\0'){
if(hashTable[＊pHashKey] == 1){
printf("%c", ＊pHashKey);
return;
}
pHashKey++;
}
}
其他同類問題還有：
判斷一個字符串中所有字符是否都不相同？代碼如下：
bool char_set[256] ;
int isUniqueCharString(const char＊ str) {
assert(str != NULL);
int len=strlen(str);
for (int i=0; i < len; ++i){
int val=str[i];
if (char_set[val]) return 0;
char_set[val]=true;
}
return 1;
}
以上算法時間復雜度為O(n)，其中n為字符串的長度。
如果要求在上述算法的基礎上進一步降低空間要求，可以使用bit-map（后續章節講解），如果假設字符串僅包含從'a'到'z'的字符，我們可以將空間需求降低到一個int。
int isUniqueChars(const char＊ str) {
assert(str != NULL);
int checker=0;
int len=strlen(str);
for (int i=0; i < len; ++i) {
int val=str[i] - 'a';
if ((checker & (1 << val)) > 0) return 0;
checker |= (1 << val);
}
return 1;
}
此題若可以改變原始字符串，也可先排序（時間復雜度為O(nlogn)），然后比對相鄰字符串是否相等。