一,概述

       1)统计每个字符串出现的个数的程序实现,利用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;
}
       特别注意:以上为C程序,不是C++

        2)利用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;
}


          3)问题:给定一个文本文件(很长的字符串)作为输入,输出最长的重复子字符串。

                例如:输入”My name is xiao tian,so you can call me xiao tian“

                           输出”xiaotian“为最长重复子字符串


                实现:”后缀数组“的简单数据结构来处理这类问题。

                            char *a="banana"

                            a[0]=banana

                            a[1]=anana

                            a[2]=nana

                            a[3]=ana

                            a[4]=na

                            a[5]=a

                  方案一:双重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,maxi,maxj;
    int maxlen=-1;
    int thislen;
    char *a="aabbbcccdddd"; 
    
    for(i=0;i<12;++i)
    {
    	for(j=i+1;j<12;++j)
    	{
	    	if((thislen=comlen(a+i,a+j))>maxlen)
	    	{
	    		printf("thislen:%d\n",thislen);
	    		maxlen=thislen;
	    		maxi=i;
	    		maxj=j;
	    	}
	    }
    	
    }
	
    for(i=maxi;i<=maxj;++i)    
       printf("%c",a[i]);
    return 0;
}
         

                  程序二:

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

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

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;
}

             4)生成随机文本

                   基于字母:下一个字符设置为 前一个字母的随机函数。或者是下一个字母是前n个字符的随机函数

                   基于单词:1>随机输出字典中单词 

                                     2>随机打开一页选一个字母,再随机打开另一页找到第一个字母后的单词为输出单词


              

二,习题

        1)许多文档系统提供了去除所有格式命令,查看原始文本表示的方法。

        2)将最常见的单词插入set容器中,然后校验每个单词是否在set容器中,有说明拼写正确,否则有可能错误

        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;
}

         5)如何将单词按频率递减顺序输出,并输出M个最常见单词(频率最高的M个单词)

               将本博客最上面,采用Map容器实现


         8)如何找出出现超过M次的最长字符串

               将字符串后缀数组写出,并排序。每次比较M个相邻字符串,求其公共字符串。

    

         9)给定两个输入文本,找出它们共有的最长字符串。

              关键代码:if(s1[i+len] == s2[j])

//求两字符串的最长公共子串
#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;

}

         利用本章的方法:给出两个字符串后缀,标记每个后缀属于第一个字符串还是第二个字符串。从相邻的N个字符串找公关字符串,保证这N个字符串两个都有。







Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐