一個字元串問題的思考

一、問題描述：

求解給定文本text 中以字元 A 開頭，字元B 結尾的子串數量。例如，文本ABCAAB 中以A開頭B結尾的子串分别為AB, ABCAAB, AAB, AB 共4個。

二、問題分析及算法設計：

字元串問題求解的通用政策：我從《TCPL》中學到的印象最深的一點，就是“逐字元處理”政策（同時注意 '\0'的處理）。

首先，使用蠻力法求解：設定兩個下标 i , j ; i 指向已搜尋到的 A 的位置， j 指向已搜尋到的B的位置。算法描述如下：

STEP1：初始化 i = 0 , j = 0. 從字元串最左邊開始。

STEP2: 用下标 i 周遊搜尋A，若搜尋到A，則記下 i 的位置并轉至STEP2；若到達字元串末尾仍沒有搜尋到，則轉至 STEP4；

STEP3：初始化 j 為 i 的下一個位置并開始搜尋B：若到達字元串末尾沒有搜尋到，則 i 移到下一個位置并轉至STEP1；若搜尋到B，則子串數目次數加一，并繼續向前搜尋，直到字元串末尾并轉至STEP1；

STEP4：搜尋結束，退出算法。

例子： ABCAAB

第一趟： A: i = 0, B: j = 1, 5 num = 2;

第二趟： A: i = 3, B: j = 5 num = 1;

第三趟： A: i = 4, B: j = 5 num = 1

共計： 2 + 1 + 1 = 4.

這樣的蠻力算法，其時間效率取決于A在字元串中出現的次數Na, T(n) = O(n * Na), n 是字元串長度。也可以從右往左搜尋，其時間效率為 T(n) = O(n * Nb), Nb是 B 在字元串中出現的次數。如果知道A和B在文本中出現的次數，那麼就可以選擇從左往右或者從右往左的周遊方式。最差情況下，例如全A串，則效率為O(n*n).

有沒有可能找到更好的算法呢？

我們知道，分治算法通常能達到 O(nlogn)的效率，隻要合并部分的時間能達到O(n) 。那麼，這個問題是否可以采用分治法來求解呢？答案是肯定的。

假設 N[left: right] 是文本 text[left:right] 中以A開始B結尾的子串數量，則整個文本中以A開始B結尾的子串數量為 N[0:n] = N[0:n/2] + N[n/2+1: n] + Na * Nb. Na 是 A 在 text[0:n/2]中出現的次數， Nb 是 B 在 text[n/2+1: n] 中出現的次數; 因為在後半段文本中的所有B都出現在前半段文本中的所有A之後(每個A與每個B都形成合乎要求的子串)，而在後半段文本中的所有A出現在前半段文本中的所有B之後（每個A與每個B都不能形成合乎要求的子串），是以，兩半段文本合并時的子串數量應該是Na * Nb.這樣，一個遞歸分治算法的模型基本就出來了，其時間複雜度為 T(n) = 2T(n/2) + O(n) = O(nlogn). 合并部分要求分别周遊字元串的兩半段，時間為O(n).

例子： N(ABCAAB) = N(ABC) + N(AAB) + 1 * 1 = 4

N(ABC) = N (A) + N(BC) + 1 * 1 = 1

N(AAB) = N(A) + N(AB) + 1 * 1 = 2

N(BC) = N(B) + N(C) + 0 * 0 = 0

N(AB) = N(A) + N(B) + 1 * 1 = 1

是以，ABCAAB 中以A開頭B結尾的子串數量有4個。

能不能找到線性時間的算法呢？看上去似乎有可能，卻又不是那麼明顯。在《程式設計珠玑I》的算法設計技術那一章裡，作者采用四種算法(本質上是三種不同類型的算法)分别進行了設計，并在小結中提到：凡是數組累加問題，都可以考慮動态規劃法來求解。那麼，是否适用于本題呢？

假設給定文本中前 n 個字元組成的文本中以A開頭B結尾的子串數量為Count[n], A出現的次數為 Na, 則前 n+1 個字元組成的文本中以A開頭B結尾的子串數量為：

[1] 若第 n+1 個字元不是結尾字元B，那麼， Count[n+1] = Count[n];

[2] 若第 n+1 個字元是結尾字元B，那麼， Count[n+1] = Count[n] + Na.

這樣，我們推導出了解的遞推關系式。更進一步地，首先初始化子串數量count及開頭字元出現次數beginNum為0；接着，從第一個字元開始，若該字元是開頭字元，則beginNum++; 若字元是結尾字元，則count += beginNum; 若該字元既不是結尾字元也不結束字元，那麼，count, beginNum均不變；

注意，當開頭字元和結尾字元相同時，上述算法會出現問題。此時，隻要計算開頭字元出現的次數Na, 則子串數量應為 Na*(Na-1)/2.

例子： ABCAAB

[1] count = 0; Na = 0;

[2] 搜尋到A： count = 0; Na = 1;

[3] 搜尋到B： count += Na → count = 1; Na = 1;

[4] 搜尋到C： count = 1; Na = 1;

[5] 搜尋到A： count = 1; Na = 2;

[6] 搜尋到A： count = 1; Na = 3;

[7] 搜尋到B： count += Na → count = 4; Na = 3;

是以，ABCAAB 中以A開頭B結尾的子串數量有4個。

三、完整程式：

/*
 * substrNum.c : 此程式計算給定文本中以給定字元開頭和結尾的字串的數目
 * 比如 ABCAAB 中， 以A開頭B結尾的子串有 AB, ABCAAB, AAB, AB 4個。
 */

#include <stdio.h>
#include <string.h>
#include <assert.h>

int substrnum(char *, char, char);
int substrnumDIV(char* text, char beginc, char endc);
int substrnumDYN(char* text, char beginc, char endc);
int substrnumREC(char* text, int leftIndex, int rightIndex, char beginc, char endc);

void test(int (*fun)(char*, char, char));

int main()
{
   printf("\n ******* 使用蠻力求解 ******** \n");
   test(substrnum);
   printf("\n ******* 使用分治法求解 ******* \n");
   test(substrnumDIV);
   printf("\n ******** 使用動态規劃法求解 ******* \n");
   test(substrnumDYN);

   return 0;
}

/*
 * substrnum: 在給定文本 text 中以字母 beginc 開頭， 字母 endc 結尾的子串
 * 蠻力法求解： 算法時間 O(n*Na) Na, 是開始字元在字元串中出現的次數。
 * 或 從右向左掃描， O(n*Nb), Nb 是結尾字元在字元串中出現的次數
 */
int substrnum(char *text, char beginc, char endc)
{
   assert(text != NULL);
   int i = 0 , j;
   int count = 0;
   char *p = text;
   while (1) {
      while (*(p+i) && (*(p+i) != beginc)) { i++; }
      if (*(p+i) == '\0')  break;  
      j = i+1;
      while (*(p+j)) {
            if (*(p+j) == endc) {
               count++;
            }
            j++;
      }
      i++;
   }
   return count;
}

/*
 * substrnumDYN: 在給定文本 text 中以字母 beginc 開頭， 字母 endc 結尾的子串
 * 使用動态規劃法求解： 
 * 若給定文本的前 n 個字元組成的字元串中所含子串數目為 count[n], 開始字元出現次數為 beginNum; 
 * 則前 n+1 個字元串中所含子串數目為 ： 
 * 1. 若第 n+1 個字元不是結尾字元， 則 count[n+1] = count[n];
 * 2. 若第 n+1 個字元是結尾字元， 則 count[n+1] = count[n] + beginNum
 * 
 */

int substrnumDYN(char *text, char beginc, char endc)
{
   assert(text != NULL);
   char *p = text;
   int count = 0; 
   int beginNum = 0;   
   while(*p) {
      if (*p == beginc) {  // 情況 1： 該字元是開始字元
         beginNum++;
      }  
      else if (*p == endc) { // 情況 2 : 該字元是結尾字元
         count += beginNum;
      }
      p++;  // 情況 1： 該字元既不是開始字元也不是結尾字元
   }
   if (beginc == endc) { // 開始字元與結尾字元相同
      return beginNum * (beginNum - 1) / 2;
   }
   return count;
}

/*
 * substrnumDIV: 在給定文本 text 中以字母 beginc 開頭， 字母 endc 結尾的子串
 * 使用分治法求解： 
 * 将給定文本分成兩端 text[0: n/2] 和 text[n/2+1: n-1], 則子串數量為：
 * N(text) = N(text[0:n/2]) + N(text[n/2+1: n-1]) + NB * NE 
 * 其中， NB是開始字元在 text[0:n/2] 中出現的次數， NE 是 結尾字元在 text[n/2: n-1] 中出現的次數
 * 算法時間：T(n) = 2T(n/2) + n = O(nlogn)
 */
int substrnumDIV(char* text, char beginc, char endc)
{
   assert(text != NULL);
   return substrnumREC(text, 0, strlen(text)+1, beginc, endc);
}

int substrnumREC(char* text, int leftIndex, int rightIndex, char beginc, char endc)
{
   if (rightIndex == leftIndex) { 
      return 0; 
   }
   else {
      int mid = (rightIndex - leftIndex + 1) / 2 + leftIndex;
      char *p = text + leftIndex;
      char *q = text + mid;
      int nb = 0;
      int ne = 0;
      while (*p && p < text+mid) {
         if (*p == beginc) {
             nb++; 
         }
         p++;
      }
      while (*q && q <= text+rightIndex) {
         if (*q == endc) { 
             ne++;
         }
         q++;
      }
      return substrnumREC(text, leftIndex, mid-1, beginc, endc) \
           + substrnumREC(text, mid, rightIndex, beginc, endc) + nb * ne;
   }
   
}

void test(int (*fun)(char* , char, char))
{
   char *text = "ABCAAB";
   printf("text = %s\n" , text);
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'B', (*fun)(text, 'A', 'B'));
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'A', (*fun)(text, 'A', 'A'));

   char *empty = "";
   printf("text = %s\n" , empty);
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'B', (*fun)(empty, 'A', 'B'));
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'A', (*fun)(empty, 'A', 'A'));

   char *two = "AA";
   printf("text = %s\n" , two);
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'B', (*fun)(two, 'A', 'B'));
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'A', (*fun)(two, 'A', 'A'));

   char *zero = "ADTFGC";
   printf("text = %s\n" , zero);
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'B', (*fun)(zero, 'A', 'B'));
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'A', (*fun)(zero, 'A', 'A'));
   
   /* NULL 參數的斷言測試，因為總是會失敗導緻程式退出，是以這裡注釋掉；可以去掉注釋檢視運作結果
   printf("以字母 %c 開頭， %c 結尾的子串數目為: %d.\n", 'A', 'B', (*fun)(NULL, 'A', 'B'));
   */
}

四、結論：

舉這樣一個字元串問題的例子是為了說明什麼呢？主要是因為，我認為它非常生動地示範了字元串問題的幾種主要思路和算法：蠻力法、分治法、動态規劃法。另外，還有一種算法，是對字元串進行預處理，比如高效字元串比對KMP算法就是這麼做的。

在這個問題中，可以首先周遊一次文本（時間是O(n)），分别将A，B出現的位置存儲在兩個數組中。仍以ABCAAB為例：首先可求得 a[]: 1, 4, 5 ; b[]: = 2, 6. 接着，求a與b的笛卡爾乘積中 (a,b) (a < b) 的個數即可。可以在O(len(a) + len(b)) 的時間内求解，隻是在周遊過程中有點技巧。是以，整個算法的時間複雜度是O(n).

一個字元串問題的思考

繼續閱讀

Understanding Steering Behaviors: Seek (行為控制-尋找)原文位址連結：http://gamedevelopment.tutsplus.com/tutorials/understanding-steering-behaviors-seek--gamedev-849位置，速度和移動計算力增加力結論

【leetcode】188. Best Time to Buy and Sell Stock IV

減繩子問題動态規劃求解

算法設計9-最小正整數問題算法設計9-最小正整數問題

POJ1013稱硬币枚舉法

為什麼普通人難以掌握資訊學奧林匹克競賽的知識？·由于資訊學奧賽涉及抽象的概念和算法，需要運用數學思維和邏輯推理能力來解決

優先隊列 PriorityQueue源碼解析PriorityQueue

判斷某日是該年第幾天

整數變換問題(C語言)--回溯法

Arab Collegiate Programming Contest 2012G. Archery(求雷達掃描的期望，區間離散化)

算法設計學習：單連結清單算法

9個offer，12家公司，35場面試，從微軟到谷歌，應屆計算機畢業生的2012求職之路[對書籍加了注釋]

短視訊美顔SDK的抖動功能是怎麼實作的

【原創】TOP k算法的簡單實作

JSON性能比對 Json BecnhMark

算法基礎遍之選擇排序算法詳解