一、统计文本中各字符串出现的个数
利用map容器，代码实现如下所示：
#include <iostream>
#include <map>
using namespace std;
int main()
{
map <string ,int> M;
map <string ,int>::iterator j;
string t[5]={"abc","dd","abc","dd","dd"};
for(int i=0;i<5;++i)
M[t[i]]++;
for(j=M.begin();j!=M.end();++j)
cout<<"<"<<j->first<<" ,"<<j->second<<">"<<endl;
return 0;
}
二、通过计算字符串的散列值并利用散列表来统计字符串个数
为了减少处理时间，可以建立散列表。其中内存分配函数malloc 被改为自定义更高效的 nmalloc和 smalloc。实现代码如下：
#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 /*乘数*/
nodeptr bin[NHASH];//散列表
unsigned int hash(char *p)//哈希函数，将每个字符串映射成小于NHASH的正整数
{ 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 = malloc(NODEGROUP*sizeof(node));
nodesleft = NODEGROUP;
}
nodesleft--;
return freenode++;
}
#define CHARGROUP 10000
int charsleft = 0;
char *freechar;
char *smalloc(int n)
{ if (charsleft < n) {
freechar = malloc(n+CHARGROUP);
charsleft = n+CHARGROUP;
}
charsleft -= 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) {//该箱子中若有 该单词，则对应count++ ,否则新建单词指针 （采取头插法）
(p->count)++;
return;
}
p = nmalloc();//本来用malloc就可以，但优化成了nmalloc
p->count = 1;
p->word = smalloc(strlen(s)+1);//本来用malloc就可以，但优化成了smalloc
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++)//输出每一个不等于NULL的箱的字符串和个数
for (p = bin[i]; p != NULL; p = p->next)
printf("%s %d\n", p->word, p->count);
return 0;
}
三、利用set容器，排序输出各个字符串（按字母表顺序）
代码如下：
#include <iostream>
#include <set>
#include <string>
using namespace std;
int main()
{
set<string> S;
set<string>::iterator j;
string t[5]={"abc","dd","abc","dd","dd"};
for(int i=0;i<5;++i)
S.insert(t[i]);
for (j = S.begin(); j != S.end(); ++j)
cout << *j << "\n";
return 0;
}
四、短语
输出短语中的重复子串，例如char *a="banana"，其最长重复子串为“ana”，通过以下两种方式来解决问题：
方案一：双重for循环比较每个字符串，找到最长重复子字符串（效率低，不可取）；
方案二：利用后缀数组，通过对其排序，然后比较相邻字符串间相同的字符个数。最后得到文本文件最长的重复子字符串。
后缀数组说明如下：
char *a="banana"; a[0]=banana; a[1]=anana; a[2]=nana; a[3]=ana; a[4]=na; a[5]=a;
方案二代码实现如下：
#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;
}
#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("%.*s\n", maxlen, a[maxi]);
return 0;
}
五、生成文本
生成随机文本的方法：1、基于字母：下一个字符设置为前一个字母的随机函数。或者是下一个字母是前n个字符的随机函数；2、基于单词：a随机输出字典中单词，b随机打开一页选一个字母，再随机打开另一页找到第一个字母后的单词为输出单词。
六、原理
（1）字符串的数据结构，set、map、hash表等；
（2）散列，平均速度快，易于实现；
（3）平衡树，C++标准模板库的set和map的大部分实现就采用平衡树；
（4）后缀数组，初始化指向文本中每个字符的指针数组，对其排序后得到后缀数组，在遍历每个数组以查找接近的字符串，也可以使用二分搜索查找单词或短语。
七、习题
（1）习题3：采用专用的内存分配器来提高散列函数的速度，即一次申请多个内存空间。只有上一次用光时，再次申请。减少了申请内存次数，代码如下：
#define NODEGROUP 1000
int nodesleft = 0;
nodeptr freenode;
nodeptr nmalloc()
{ if (nodesleft == 0) {
freenode = malloc(NODEGROUP*sizeof(node));
nodesleft = NODEGROUP;
}
nodesleft--;
return freenode++;
}
#define CHARGROUP 10000
int charsleft = 0;
char *freechar;
char *smalloc(int n)
{ if (charsleft < n) {
freechar = malloc(n+CHARGROUP);
charsleft = n+CHARGROUP;
}
charsleft -= n;
freechar += n;
return freechar - n;
}
（2）习题5：将单词按频率递减的顺序输出，如何实现？若仅输出M个最常见的单词呢？
可在C++（map）程序中添加另一个映射，将一组单词跟他们的计数联系起来。在C程序中，我们可以根据计数对数组进行排序，然后对其迭代（由于一些单词的计数会比较大，数组应该比输入文件小得多）。对于常见的文档，我们可以用关键字索引，并保存一个在一定范围内（如1~1000）的计数的链表数组，从而实现对M个常见单词的输出。
（3）习题8：如何找出出现超过M次的最长字符串。
子数组a[i...i+M]表示M+1个字符串。由于数组是有序的，我们可以通过调用在第一个和最后一个字符串上调用comlen函数来快速确定这M+1个字符串共有的字符数：comlen(a[i], a[i+M]);
（4）习题9：给定两个输入文本，找到他们共有的最长字符串。
当第一个字符串读入数组c，记录其结束的位置并在其最后填入空字符；然后读入第二个字符串并进行相同的处理。跟以前一样进行排序。扫描数组时，使用“异或”操作来确保恰有一个字符串是从过渡点前面开始的。
利用本章的方法：给出两个字符串后缀，标记每个后缀属于第一个字符串还是第二个字符串。从相邻的N个字符串找公关字符串，保证这N个字符串两个都有。代码实现如下：
//求两字符串的最长公共子串
#include<stdio.h>
#include<string.h>
char * maxsamesubstring(char *s1,char *s2)
{
int i,j,len,maxlen,index,maxindex;
maxlen=0; //初始化最长公共子串的长度
maxindex=0; //初始化最长公共子串的位置
len=0; //当前公共子串的长度
for(i=0;s1[i]!='\0';i++)
for(j=0;s2[j]!='\0';j++)
if(s1[i+len]==s2[j])
{
if(!len)//len=0 的时候执行（第一次执行）
{
index=j; //记下公共子串的起始位置
}
len++;
}
else if(len)
{
if(maxlen<len) //经过一次扫描找到了最长公共子串
{
maxlen=len;
maxindex=index;
}
len=0; //进行下一次的扫描
}
char *p=new char[maxlen+1];
strncpy(p,s2+maxindex,maxlen); //把最长公共字符串复制到p所指的空间
p[maxlen+1]='\0'; //置串结束标志
return p;
}
int main()
{
char *s1="president hujintao",*s2="times jin",*sub;
sub=maxsamesubstring(s1,s2);
printf("%s\n",sub);
return 0;
}
（5）习题14：使用散列函数对马尔科夫程序提速：
下面的函数对k个单词组成的序列进行了散列，其中每个单词都以空字符结束：
unsigned int hash(char* p)
{
unsigned int h = 0;
int n;
for(n = k; n > 0; p++)
{
h = NULT * h + *p;
if(*p == 0)
n--;
}
return h % NHASH;
}
可用这个散列函数取代马尔科夫文本生成算法中的二分搜索，使得平均时间从O(nlogn)降到了O(n)。改程序在散列表中为元素使用了链表表示法，只增加了nwords个32位整数的额外空间，其中nwords是输入中的单词个数。
修改后的马尔科夫程序如下所示：
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define NHASH 49979
#define MULT 31
#define MAXWORDS 80000
char inputchars[4300000];//存储输入数据
char *word[MAXWORDS];//后缀数组
int nword=0;//记录单词数
int k=2;//2阶
int next[MAXWORDS];//用于构建hash表
int bin[NHASH];
//以k个单词为单位，进行hash
unsigned int hash(char* str){
int n;
unsigned int h=0;
char* p=str;
for(n=k;n>0;++p){
h=MULT*h+*p;
if(*p=='\0')
--n;
}
return h%NHASH;
}
//比较前k个单词的大小
int wordncmp(char* p,char *q){
int n;
for(n=k;*p==*q;++p,++q){
if(*p=='\0'&&(--n)==0)
return 0;
}
return *p-*q;
}
//从当前单词出发，跳过前n个单词
char* skip(char* p,int n){
for(;n>0;++p){
if(*p=='\0')
--n;
}
return p;
}
int main(){
int i,j;
//步骤1：构建后缀数组
word[0]=inputchars;
//scanf以空格作为分隔符, 并且自动加上'\0'
while((scanf("%s",word[nword]))!=EOF){
word[nword+1]=word[nword]+strlen(word[nword])+1;
++nword;
}
//附加k个空字符,保证wordncmp()正确（感觉不需要这个）
for(i=0;i<k;++i)
word[nword][i]='\0';
//步骤2：构建hash table
//初始化hash table
for(i=0;i<NHASH;++i)
bin[i]=-1;
//hash表采用前插的方式。例如：word[0], word[1], word[5]拥有相同的hash值15
//则： bin[15](5)->next[5](1)->next[1](0)->next[0](-1)
for(i=0;i<=nword-k;++i) {
j=hash(word[i]);
next[i]=bin[j];
bin[j]=i;
}
//步骤3：生成随机文本
int wordsleft;//生成单词数
int psofar;
char *phrase,*p;
phrase=inputchars;
for(wordsleft=10000;wordsleft>0;--wordsleft){
psofar=0;
for(j=bin[hash(phrase)];j>=0;j=next[j])
//在hash值相同的项中找出字符串值相同的后缀数组表项，根据概率选择一个
if(wordncmp(phrase,word[j])==0&&rand()%(++psofar)==0)
p=word[j];
//将phrase重新设置
phrase=skip(p,1);
//输出符合要求单词的后面第k个单词
if(strlen(skip(phrase,k-1))==0)
break;
printf("%s\n",skip(phrase,k-1));
}
return 0;
}