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

一、单词
（1）为文档中包含的单词生成一个列表？
解答：
    方法一：用到标准模板库中的sets和strings

#include <iostream>
#include <set>
#include <string>

using namespace std;

int main(int argc, char **argv)
{
    set<string> str;
    set<string>::iterator iter;
    string t;
    while(cin >> t)
    {
        str.insert(t);
    }
    for(iter = str.begin(); iter != str.end(); iter++)
    {
        cout << *iter << endl;
    }
    return 0;
}

    while循环读取输入并将每个单词插入集合str（忽略重复的单词），然后for循环迭代整个集合，并按排好的顺序输出单词。

（2）为单词进行计数
    方法一：用标准模板库中的map将整个计数与每个字符串联系起来

#include <iostream>
#include <map>
#include <string>

using namespace std;

int main(int argc, char **argv)
{
    map<string, int> m;
    map<string, int>::iterator iter;
    string t;
    while(cin >> t)
    {
        m[t]++;
    }
    for(iter = m.begin(); iter != m.end(); iter++)
    {
        cout << iter->first << " " << iter->second << endl;
    }
    return 0;
}

    方法二：为了减少处理时间，可以自己建立散列表

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

typedef struct node *nodeptr;
typedef struct node
{
    char *word;
    int count;
    nodeptr next;
}node;

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

unsigned int hash(char *p)
{
    unsigned int h = 0;
    for( ; *p != ''; p++)
    {
        h = MULT * h + *p;
    }
    return h % NHASH;
}

#define NODEGROUP    1000
int nodesleft = 0;
nodeptr freenode;

nodeptr nmalloc()
{
    if(nodesleft == 0)
    {
        freenode = (nodeptr)malloc(NODEGROUP *sizeof(node));
        nodesleft = NODEGROUP;
    }
    nodesleft--;
    return freenode++;
}

#define CHARGROUP    10000
int charleft = 0;
char *freechar;

char *smalloc(int n)
{
    if(charleft < n)
    {
        freechar = (char *)malloc(n + CHARGROUP);
        charleft = n + CHARGROUP;
    }
    charleft -= n;
    freechar += n;
    return freechar - n;
}

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

    p = nmalloc();
    p->count = 1;
    p->word = smalloc(strlen(s) + 1);
    strcpy(p->word, s);
    p->next = bin[h];    //头插法
    bin[h] = p;
}


int main()
{
    int i;
    nodeptr p;
    char buf[100];
    for(i = 0; i < NHASH; i++)
    {
        bin[i] = NULL;
    }
    while(scanf("%s", buf) != EOF)
    {
        incword(buf);
    }
    for(i = 0; i < NHASH; i++)
    {
        for(p = bin[i]; p != NULL; p = p->next)
        {
            printf("%s %dn", p->word, p->count);
        }
    }
    return 0;
}

    前面介绍了表示单词集合的两种方法。平衡搜索树将字符串看作是不可分割的对象进行操作，标准模板库的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循环依次比较每个字符串，找到最长重复子字符串

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

//找到两个字符串公共部分的长度
int comlen(char *p, char *q)
{
    int i = 0;
    while (*p && (*p++ == *q++))
    {
        i++;
    }
    return i;
}

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

    for(i = 0; i < length; i++)
    {
        for(j = i + 1; j < length; j++)
        {
            currentlen = comlen(str + i, str + j);
            if(currentlen > maxlen)
            {
                maxlen = currentlen;
                maxi = i;
                maxj = j;
            }
        }
    }

    for(i = 0; i < maxlen; i++)
    {
        printf("%c", str[maxi + i]);
    }
    printf("n");
    return 0;
}

    方法二：采用后缀数组来处理该问题
    我们的程序最多处理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)。

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

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

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

#define M 1
#define MAXN 5000000
char c[MAXN], *a[MAXN];

int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
    while ((ch = getchar()) != EOF) {
        a[n] = &c[n];
        c[n++] = ch;
    }
    c[n] = 0;
    qsort(a, n, sizeof(char *), pstrcmp);//快速排序
    for (i = 0; i < n-M; i++)
        if (comlen(a[i], a[i+M]) > maxlen) {//比较相邻字符串相同个数
            maxlen = comlen(a[i], a[i+M]);
            maxi = i;
        }
    printf("%.*sn", maxlen, a[maxi]);
    return 0;
}

三、生成随机文本
    基于字母：下一个字母设置为前一个字母的随机函数，或者下一个字母设置为前k个字母的随机函数。

/* Copyright (C) 2000 Lucent Technologies */
/* Modified from markov.c in 'Programming Pearls' by Jon Bentley */

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

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

char x[5000000];

int main()
{    int c, i, eqsofar, max, n = 0, k = 5;
    char *p, *nextp, *q;
    while ((c = getchar()) != EOF)
    {
        x[n++] = c;
    }
    x[n] = 0;
    p = x;
    srand(1);
    for (max = 2000; max > 0; max--)
    {
        eqsofar = 0;
        for (q = x; q < x + n - k + 1; q++)
        {
            for (i = 0; i < k && *(p+i) == *(q+i); i++)
                ;
            if (i == k)
            {
                if (rand() % ++eqsofar == 0)
                {
                    nextp = q;
                }
            }
        }
        c = *(nextp+k);
        if (c == 0)
        {
            break;
        }
        putchar(c);
        p = nextp+1;
    }
    return 0;
}

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

/* Copyright (C) 1999 Lucent Technologies */
/* From 'Programming Pearls' by Jon Bentley */

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

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

char inputchars[4300000];
char *word[800000];
int nword = 0;
int k = 2;

int wordncmp(char *p, char* q)
{
    int n = k;
    for ( ; *p == *q; p++, q++)
    {
        if (*p == 0 && --n == 0)
            return 0;
    }
    return *p - *q;
}

int sortcmp(char **p, char **q)
{
    return wordncmp(*p, *q);
}

char *skip(char *p, int n)
{    for ( ; n > 0; p++)
    {
        if (*p == 0)
            n--;
    }
    return p;
}

int main()
{
    int i, wordsleft = 10000, l, m, u;
    char *phrase, *p;

    word[0] = inputchars;
    while (scanf("%s", word[nword]) != EOF)
    {
        word[nword+1] = word[nword] + strlen(word[nword]) + 1;
        nword++;
    }

    for (i = 0; i < k; i++)
        word[nword][i] = 0;
    for (i = 0; i < k; i++)
        printf("%sn", word[i]);

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

    phrase = inputchars;
    for ( ; wordsleft > 0; wordsleft--)
    {
        l = -1;
        u = nword;
        while (l+1 != u)
        {
            m = (l + u) / 2;
            if (wordncmp(word[m], phrase) < 0)
                l = m;
            else
                u = m;
        }
        for (i = 0; wordncmp(phrase, word[u+i]) == 0; i++)
        {
            if (rand() % (i+1) == 0)
            {
                p = word[u+i];
            }
        }
        phrase = skip(p, 1);
        if (strlen(skip(phrase, k-1)) == 0)
        {
            break;
        }
        printf("%sn", skip(phrase, k-1));
    }
    return 0;
}

    关于生成随机文本的代码，需要慢慢的理解其思想，先记录下来，慢慢体会。