一个字符串问题的思考 .

╰+攻爆jí腚メ 2022-05-22 00:48 139阅读 0赞

**一、 问题描述：**  
  
        求解给定文本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个。  
  
**三、 完整程序：**

**\[cpp\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  /\* 
2.   \* substrNum.c : 此程序计算给定文本中以给定字符开头和结尾的字串的数目 
3.   \* 比如 ABCAAB 中， 以A开头B结尾的子串有 AB, ABCAAB, AAB, AB 4个。 
4.   \*/  
5.    
6.  \#include <stdio.h>   
7.  \#include <string.h>    
8.  \#include <assert.h>   
9.    
10. int substrnum(char \*, char, char);  
11. int substrnumDIV(char\* text, char beginc, char endc);  
12. int substrnumDYN(char\* text, char beginc, char endc);  
13. int substrnumREC(char\* text, int leftIndex, int rightIndex, char beginc, char endc);  
14.   
15. void test(int (\*fun)(char\*, char, char));  
16.   
17. int main()  
18. \{  
19.    printf("\\n \*\*\*\*\*\*\* 使用蛮力求解 \*\*\*\*\*\*\*\* \\n");  
20.    test(substrnum);  
21.    printf("\\n \*\*\*\*\*\*\* 使用分治法求解 \*\*\*\*\*\*\* \\n");  
22.    test(substrnumDIV);  
23.    printf("\\n \*\*\*\*\*\*\*\* 使用动态规划法求解 \*\*\*\*\*\*\* \\n");  
24.    test(substrnumDYN);  
25.   
26.    return 0;  
27. \}  
28.   
29. /\* 
30.  \* substrnum: 在给定文本 text 中以字母 beginc 开头， 字母 endc 结尾的子串 
31.  \* 蛮力法求解： 算法时间 O(n\*Na) Na, 是开始字符在字符串中出现的次数。 
32.  \* 或 从右向左扫描， O(n\*Nb), Nb 是结尾字符在字符串中出现的次数 
33.  \*/  
34. int substrnum(char \*text, char beginc, char endc)  
35. \{  
36.    assert(text != NULL);  
37.    int i = 0 , j;  
38.    int count = 0;  
39.    char \*p = text;  
40.    while (1) \{  
41.       while (\*(p+i) && (\*(p+i) != beginc)) \{ i++; \}  
42.       if (\*(p+i) == '\\0')  break;    
43.       j = i+1;  
44.       while (\*(p+j)) \{  
45.             if (\*(p+j) == endc) \{  
46.                count++;  
47.             \}  
48.             j++;  
49.       \}  
50.       i++;  
51.    \}  
52.    return count;  
53. \}  
54.   
55. /\* 
56.  \* substrnumDYN: 在给定文本 text 中以字母 beginc 开头， 字母 endc 结尾的子串 
57.  \* 使用动态规划法求解：  
58.  \* 若给定文本的前 n 个字符组成的字符串中所含子串数目为 count\[n\], 开始字符出现次数为 beginNum;  
59.  \* 则前 n+1 个字符串中所含子串数目为 ：  
60.  \* 1. 若第 n+1 个字符不是结尾字符， 则 count\[n+1\] = count\[n\]; 
61.  \* 2. 若第 n+1 个字符是结尾字符， 则 count\[n+1\] = count\[n\] + beginNum 
62.  \*  
63.  \*/  
64.   
65. int substrnumDYN(char \*text, char beginc, char endc)  
66. \{  
67.    assert(text != NULL);  
68.    char \*p = text;  
69.    int count = 0;   
70.    int beginNum = 0;     
71.    while(\*p) \{  
72.       if (\*p == beginc) \{  // 情况 1： 该字符是开始字符   
73.          beginNum++;  
74.       \}    
75.       else if (\*p == endc) \{ // 情况 2 : 该字符是结尾字符   
76.          count += beginNum;  
77.       \}  
78.       p++;  // 情况 1： 该字符既不是开始字符也不是结尾字符    
79.    \}  
80.    if (beginc == endc) \{ // 开始字符与结尾字符相同   
81.       return beginNum \* (beginNum - 1) / 2;  
82.    \}  
83.    return count;  
84. \}  
85.   
86. /\* 
87.  \* substrnumDIV: 在给定文本 text 中以字母 beginc 开头， 字母 endc 结尾的子串 
88.  \* 使用分治法求解：  
89.  \* 将给定文本分成两端 text\[0: n/2\] 和 text\[n/2+1: n-1\], 则子串数量为： 
90.  \* N(text) = N(text\[0:n/2\]) + N(text\[n/2+1: n-1\]) + NB \* NE  
91.  \* 其中， NB是开始字符在 text\[0:n/2\] 中出现的次数， NE 是 结尾字符在 text\[n/2: n-1\] 中出现的次数 
92.  \* 算法时间：T(n) = 2T(n/2) + n = O(nlogn) 
93.  \*/  
94. int substrnumDIV(char\* text, char beginc, char endc)  
95. \{  
96.    assert(text != NULL);  
97.    return substrnumREC(text, 0, strlen(text)+1, beginc, endc);  
98. \}  
99.   
100. int substrnumREC(char\* text, int leftIndex, int rightIndex, char beginc, char endc)  
101. \{  
102.    if (rightIndex == leftIndex) \{   
103.       return 0;   
104.    \}  
105.    else \{  
106.       int mid = (rightIndex - leftIndex + 1) / 2 + leftIndex;  
107.       char \*p = text + leftIndex;  
108.       char \*q = text + mid;  
109.       int nb = 0;  
110.       int ne = 0;  
111.       while (\*p && p < text+mid) \{  
112.          if (\*p == beginc) \{  
113.              nb++;   
114.          \}  
115.          p++;  
116.       \}  
117.       while (\*q && q <= text+rightIndex) \{  
118.          if (\*q == endc) \{   
119.              ne++;  
120.          \}  
121.          q++;  
122.       \}  
123.       return substrnumREC(text, leftIndex, mid-1, beginc, endc) \\  
124.            + substrnumREC(text, mid, rightIndex, beginc, endc) + nb \* ne;  
125.    \}  
126.      
127. \}  
128.   
129. void test(int (\*fun)(char\* , char, char))  
130. \{  
131.    char \*text = "ABCAAB";  
132.    printf("text = %s\\n" , text);  
133.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'B', (\*fun)(text, 'A', 'B'));  
134.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'A', (\*fun)(text, 'A', 'A'));  
135.   
136.    char \*empty = "";  
137.    printf("text = %s\\n" , empty);  
138.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'B', (\*fun)(empty, 'A', 'B'));  
139.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'A', (\*fun)(empty, 'A', 'A'));  
140.   
141.    char \*two = "AA";  
142.    printf("text = %s\\n" , two);  
143.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'B', (\*fun)(two, 'A', 'B'));  
144.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'A', (\*fun)(two, 'A', 'A'));  
145.   
146.    char \*zero = "ADTFGC";  
147.    printf("text = %s\\n" , zero);  
148.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'B', (\*fun)(zero, 'A', 'B'));  
149.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'A', (\*fun)(zero, 'A', 'A'));  
150.      
151.    /\* NULL 参数的断言测试，因为总是会失败导致程序退出，所以这里注释掉；可以去掉注释查看运行结果 
152.    printf("以字母 %c 开头， %c 结尾的子串数目为: %d.\\n", 'A', 'B', (\*fun)(NULL, 'A', 'B')); 
153.    \*/  
154. \}

/*
     * 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).

转载自：[http://blog.csdn.net/shuqin1984/article/details/6544265][http_blog.csdn.net_shuqin1984_article_details_6544265]

[view plain]: http://blog.csdn.net/shuqin1984/article/details/6544265#
[http_blog.csdn.net_shuqin1984_article_details_6544265]: http://blog.csdn.net/shuqin1984/article/details/6544265