编程珠玑——第十五章字符串

2540阅读　0评论2013-06-15　梦醒潇湘love
分类：C/C++


一、单词
（1）为文档中包含的单词生成一个列表？
解答：
    方法一：用到标准模板库中的sets和strings
  1. #include <iostream>
  2. #include <set>
  3. #include <string>

  5. using namespace std;

  7. int main(int argc, char **argv)
  8. {
  9.     set<string> str;
  10.     set<string>::iterator iter;
  11.     string t;
  12.     while(cin >> t)
  13.     {
  14.         str.insert(t);
  15.     }
  16.     for(iter = str.begin(); iter != str.end(); iter++)
  17.     {
  18.         cout << *iter << endl;
  19.     }
  20.     return 0;
  21. }
    while循环读取输入并将每个单词插入集合str（忽略重复的单词），然后for循环迭代整个集合，并按排好的顺序输出单词。

（2）为单词进行计数
    方法一：用标准模板库中的map将整个计数与每个字符串联系起来
  1. #include <iostream>
  2. #include <map>
  3. #include <string>

  5. using namespace std;

  7. int main(int argc, char **argv)
  8. {
  9.     map<string, int> m;
  10.     map<string, int>::iterator iter;
  11.     string t;
  12.     while(cin >> t)
  13.     {
  14.         m[t]++;
  15.     }
  16.     for(iter = m.begin(); iter != m.end(); iter++)
  17.     {
  18.         cout << iter->first << " " << iter->second << endl;
  19.     }
  20.     return 0;
  21. }
    方法二：为了减少处理时间，可以自己建立散列表
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>

  5. typedef struct node *nodeptr;
  6. typedef struct node
  7. {
  8.     char *word;
  9.     int count;
  10.     nodeptr next;
  11. }node;

  13. #define NHASH    29989    //圣经中有29131个不同的单词，用跟29131最接近的质数作为散列表的大小
  14. #define MULT 31            //hash时用到的乘数
  15. nodeptr bin[NHASH];        //散列表

  17. unsigned int hash(char *p)
  18. {
  19.     unsigned int h = 0;
  20.     for( ; *p != ''; p++)
  21.     {
  22.         h = MULT * h + *p;
  23.     }
  24.     return h % NHASH;
  25. }

  27. #define NODEGROUP    1000
  28. int nodesleft = 0;
  29. nodeptr freenode;

  31. nodeptr nmalloc()
  32. {
  33.     if(nodesleft == 0)
  34.     {
  35.         freenode = (nodeptr)malloc(NODEGROUP *sizeof(node));
  36.         nodesleft = NODEGROUP;
  37.     }
  38.     nodesleft--;
  39.     return freenode++;
  40. }

  42. #define CHARGROUP    10000
  43. int charleft = 0;
  44. char *freechar;

  46. char *smalloc(int n)
  47. {
  48.     if(charleft < n)
  49.     {
  50.         freechar = (char *)malloc(n + CHARGROUP);
  51.         charleft = n + CHARGROUP;
  52.     }
  53.     charleft -= n;
  54.     freechar += n;
  55.     return freechar - n;
  56. }

  58. //增加原先存在的单词的计数值，若之前没有该单词，则对计数器初始化
  59. void incword(char *s)
  60. {
  61.     nodeptr p;
  62.     int h = hash(s);    //找到与单词对应的箱
  63.     for(p = bin[h]; p != NULL; p = p->next)
  64.     {
  65.         if(strcmp(s, p->word) == 0)
  66.         {
  67.             (p->count)++;
  68.             return;
  69.         }
  70.     }

  72.     p = nmalloc();
  73.     p->count = 1;
  74.     p->word = smalloc(strlen(s) + 1);
  75.     strcpy(p->word, s);
  76.     p->next = bin[h];    //头插法
  77.     bin[h] = p;
  78. }


  81. int main()
  82. {
  83.     int i;
  84.     nodeptr p;
  85.     char buf[100];
  86.     for(i = 0; i < NHASH; i++)
  87.     {
  88.         bin[i] = NULL;
  89.     }
  90.     while(scanf("%s", buf) != EOF)
  91.     {
  92.         incword(buf);
  93.     }
  94.     for(i = 0; i < NHASH; i++)
  95.     {
  96.         for(p = bin[i]; p != NULL; p = p->next)
  97.         {
  98.             printf("%s %dn", p->word, p->count);
  99.         }
  100.     }
  101.     return 0;
  102. }
    前面介绍了表示单词集合的两种方法。平衡搜索树将字符串看作是不可分割的对象进行操作，标准模板库的set和map中大部分实现都使用这种结构。平衡搜索树中的元素始终处于有序状态，从而很容易的指向寻找前驱结点或按顺序输出元素之类的操作。另一方面，散列则需要深入字符串的内部，计算散列函数并将关键字散列到一个较大的表中。散列方法的平均速度很快，但缺乏平衡树提供的最坏情况的保证，也不能支持其他涉及顺序的操作。

二、短语
    给定一个文本文件作为输入，插在其中最长的重复子字符串。例如，“Ask not what your country can do for you, but what you can do for your country”中最长的重复字符串是“can do for you”，第二长的是“your country”。
    
    方法一：双重for循环依次比较每个字符串，找到最长重复子字符串
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <stdio.h>

  5. //找到两个字符串公共部分的长度
  6. int comlen(char *p, char *q)
  7. {    
  8.     int i = 0;
  9.     while (*p && (*p++ == *q++))
  10.     {
  11.         i++;
  12.     }
  13.     return i;
  14. }

  16. int main()
  17. {
  18.     int i, j;
  19.     int maxi, maxj;
  20.     int currentlen, maxlen = -1;
  21.     char *str = "ask not what your country can do for you, but what you can do for your country";
  22.     int length = strlen(str);

  24.     for(i = 0; i < length; i++)
  25.     {
  26.         for(j = i + 1; j < length; j++)
  27.         {
  28.             currentlen = comlen(str + i, str + j);
  29.             if(currentlen > maxlen)
  30.             {
  31.                 maxlen = currentlen;
  32.                 maxi = i;
  33.                 maxj = j;
  34.             }
  35.         }
  36.     }

  38.     for(i = 0; i < maxlen; i++)
  39.     {
  40.         printf("%c", str[maxi + i]);
  41.     }
  42.     printf("n");
  43.     return 0;
  44. }

    方法二：采用后缀数组来处理该问题
    我们的程序最多处理MAXN个字符，这些字符存储在数组c中。
    #define MAXN  50000
    char c[MAXN], *a[MAXN];
    我们使用一个称为“后缀数组”的数据结构，这个结构是一个字符指针数组，记为a。读取输入时，我们对a进行初始化，使得每个元素指向输入字符串中的相应字符：
    while(ch  = getchar() != EOF)
    {
            a[n] = &c[n];
            c[n] = ch;
    }
    c[n] = 0;

    元素a[0]指向整个字符串，下一个元素指向从第二个字符开始的数组后缀，等等。对于输入字符串“banana”，该数组能够表示如下后缀：
                            char *a="banana"
                            a[0]=banana
                            a[1]=anana
                            a[2]=nana
                            a[3]=ana
                            a[4]=na
                            a[5]=a
    如果某个长字符串在数组c中出现了两次，那么它将出现在两个不同的后缀中，因此我们队数组进行排序以寻找相同的后缀。“banana”数组排序为：
                            a[0]=a
                            a[1]=ana
                            a[2]=anana
                            a[3]=banana
                            a[4]=na
                            a[5]=nana
    然后就可以扫描数组，通过比较相邻元素来找出最长的重复字符串。
    该方法由于排序的存在，时间复杂度为O(nlogn)。
  1. #include <stdlib.h>
  2. #include <string.h>
  3. #include <stdio.h>

  5. int pstrcmp(char **p, char **q)
  6. { return strcmp(*p, *q); }//只能比较字符串,两个字符串自左向右逐个字符相比（按ASCII值大小相比较），直到出现不同的字符或遇''为止。

  8. int comlen(char *p, char *q)//返回两个参数共同部分的长度
  9. {    int i = 0;
  10.     while (*p && (*p++ == *q++))
  11.         i++;
  12.     return i;
  13. }

  15. #define M 1
  16. #define MAXN 5000000
  17. char c[MAXN], *a[MAXN];

  19. int main()
  20. { int i, ch, n = 0, maxi, maxlen = -1;
  21.     while ((ch = getchar()) != EOF) {
  22.         a[n] = &c[n];
  23.         c[n++] = ch;
  24.     }
  25.     c[n] = 0;
  26.     qsort(a, n, sizeof(char *), pstrcmp);//快速排序
  27.     for (i = 0; i < n-M; i++)
  28.         if (comlen(a[i], a[i+M]) > maxlen) {//比较相邻字符串相同个数
  29.             maxlen = comlen(a[i], a[i+M]);
  30.             maxi = i;
  31.         }
  32.     printf("%.*sn", maxlen, a[maxi]);
  33.     return 0;
  34. }

三、生成随机文本
    基于字母：下一个字母设置为前一个字母的随机函数，或者下一个字母设置为前k个字母的随机函数。
  1. /* Copyright (C) 2000 Lucent Technologies */
  2. /* Modified from markov.c in 'Programming Pearls' by Jon Bentley */

  4. /* markovlet.c -- generate letter-level random text from input text
  5.     Alg: Store text in an array on input
  6.          Scan complete text for each output character
  7.             (Randomly select one matching k-gram)
  8.  */

  10. #include <stdio.h>
  11. #include <stdlib.h>

  13. char x[5000000];

  15. int main()
  16. {    int c, i, eqsofar, max, n = 0, k = 5;
  17.     char *p, *nextp, *q;
  18.     while ((c = getchar()) != EOF)
  19.     {
  20.         x[n++] = c;
  21.     }
  22.     x[n] = 0;
  23.     p = x;
  24.     srand(1);
  25.     for (max = 2000; max > 0; max--)
  26.     {
  27.         eqsofar = 0;
  28.         for (q = x; q < x + n - k + 1; q++)
  29.         {
  30.             for (i = 0; i < k && *(p+i) == *(q+i); i++)
  31.                 ;
  32.             if (i == k)
  33.             {
  34.                 if (rand() % ++eqsofar == 0)
  35.                 {
  36.                     nextp = q;
  37.                 }
  38.             }
  39.         }
  40.         c = *(nextp+k);
  41.         if (c == 0)
  42.         {
  43.             break;
  44.         }
  45.         putchar(c);
  46.         p = nextp+1;
  47.     }
  48.     return 0;
  49. }

    基于单词：
    方法一：最笨的方法是随机输出字典中的单词；
    方法二：稍微好点的方法是读取一个文档，对每个单词进行计数，然后根据适当的概率选择下一个输出的单词；
    方法三：如果使用在生成下一个单词时考虑前面几个单词的马尔科夫链，可以得到更加令人感兴趣的文本；
    下面是香农的算法：以构建【字母级别的一阶文本】为例，随机打开一本书并在该页随机选择一个字母记录下来。然后翻到另一页开始读，直到遇到该字母，此时记录喜爱其后面的那个字母。再翻到另外一页搜索上述第二个字母并记录其后面的那个字母。依次类推。对于【字母级别的1阶、2阶文本和单词级别的0阶、1阶文本】，处理过程类似。
  1. /* Copyright (C) 1999 Lucent Technologies */
  2. /* From 'Programming Pearls' by Jon Bentley */

  4. /* markov.c -- generate random text from input document */

  6. #include <stdio.h>
  7. #include <stdlib.h>
  8. #include <string.h>

  10. char inputchars[4300000];
  11. char *word[800000];
  12. int nword = 0;
  13. int k = 2;

  15. int wordncmp(char *p, char* q)
  16. {    
  17.     int n = k;
  18.     for ( ; *p == *q; p++, q++)
  19.     {
  20.         if (*p == 0 && --n == 0)
  21.             return 0;
  22.     }
  23.     return *p - *q;
  24. }

  26. int sortcmp(char **p, char **q)
  27. {    
  28.     return wordncmp(*p, *q);
  29. }

  31. char *skip(char *p, int n)
  32. {    for ( ; n > 0; p++)
  33.     {
  34.         if (*p == 0)
  35.             n--;
  36.     }    
  37.     return p;
  38. }

  40. int main()
  41. {    
  42.     int i, wordsleft = 10000, l, m, u;
  43.     char *phrase, *p;
  44.     
  45.     word[0] = inputchars;
  46.     while (scanf("%s", word[nword]) != EOF)
  47.     {
  48.         word[nword+1] = word[nword] + strlen(word[nword]) + 1;
  49.         nword++;
  50.     }

  52.     for (i = 0; i < k; i++)
  53.         word[nword][i] = 0;
  54.     for (i = 0; i < k; i++)
  55.         printf("%sn", word[i]);

  57.     qsort(word, nword, sizeof(word[0]), sortcmp);

  59.     phrase = inputchars;
  60.     for ( ; wordsleft > 0; wordsleft--)
  61.     {
  62.         l = -1;
  63.         u = nword;
  64.         while (l+1 != u)
  65.         {
  66.             m = (l + u) / 2;
  67.             if (wordncmp(word[m], phrase) < 0)
  68.                 l = m;
  69.             else
  70.                 u = m;
  71.         }
  72.         for (i = 0; wordncmp(phrase, word[u+i]) == 0; i++)
  73.         {
  74.             if (rand() % (i+1) == 0)
  75.             {
  76.                 p = word[u+i];
  77.             }
  78.         }
  79.         phrase = skip(p, 1);
  80.         if (strlen(skip(phrase, k-1)) == 0)
  81.         {
  82.             break;
  83.         }
  84.         printf("%sn", skip(phrase, k-1));
  85.     }
  86.     return 0;
  87. }
    关于生成随机文本的代码，需要慢慢的理解其思想，先记录下来，慢慢体会。






    
上一篇：有n个长为m+1的字符串，求前后m个字符匹配所能形成的最长字符串链。
下一篇：查找出现M次的最长的字符串