编程珠玑

珠玑"/>

编程珠玑

本章讨论了一些字符串处理的算法

1,最长重复子串

   使用了后缀字符串的技巧

#define  MAX_TEXT_LEN 2000000
#define  FORWARD_LEN 2int getMaxCmp(const wchar_t* p1,const wchar_t* p2)
{int n=0;while(p1[n]==p2[n])n++;return n;
}
wstring maxCmpText( const char* file )
{wchar_t* text=new wchar_t[MAX_TEXT_LEN];wchar_t** textp=new wchar_t*[MAX_TEXT_LEN];for (int i=0;i<MAX_TEXT_LEN;i++){textp[i]=text+i;}//
    memset(text,0,MAX_TEXT_LEN*sizeof(wchar_t));setlocale(LC_ALL,"chs");FILE* f=fopen(file,"r");wchar_t *curPos=text;int len=0;while(fgetws(curPos,1000,f)){len+=wcslen(curPos);curPos=text+len;}//wprintf(L"%s",text);printf("长度:%d\n",len);std::sort(textp,textp+len,[](wchar_t* p1,wchar_t* p2){return wcscmp(p1,p2)<0;});int nMaxCmp=0;wchar_t* pMax=text;for (int i=0;i<len-1;i++){int tmp=getMaxCmp(textp[i],textp[i+1]);if (tmp>nMaxCmp){pMax=textp[i];nMaxCmp=tmp;}}wprintf(L"%d\n",nMaxCmp);wstring st(pMax,pMax+nMaxCmp);wprintf(L"%s\n",st.c_str());return L"";
}

让我们来检查一下史记中的最长子串是什么?结果如下:

果不其然,由于史记里面的<孝武本纪>基本上是摘抄<封禅书>的内容,因此最长重复子串就在<封禅书>里面

但是为什么只有171个字符呢?应该更大才对,我看了一下史记,在开始处分别是"祀其名山川"和"礼其名山川",结尾处是"则祠泰一"和"则祠太一",为什么是这样呢?既然是摘抄的,应该是一样的啊

话说回来,我很想看看原本的<孝武本纪>,看看司马迁是如何描写汉武帝的,太史公肯定有其独到的观点

2,随机文本

　书上使用单词为单位生成随机文本,我生成汉字,直接以每个字输出,算法要简单一些

　这里的重点是二分搜索和随机字符的算法,使用了前几章的习题里面的技巧:二分搜索如何搜索满足条件的第一个元素?如何在不知道元素总数的情况下随机选择一个?

#define  MAX_TEXT_LEN 2000000
#define  FORWARD_LEN 2int getMaxCmp(const wchar_t* p1,const wchar_t* p2)
{int n=0;while(p1[n]==p2[n])n++;return n;
}
int wordCmp(const wchar_t* p1,const wchar_t* p2)
{for (int i=0;i<FORWARD_LEN-1;i++){if(p1[i]!=p2[i])return p1[i]-p2[i];}return 0;
}
wstring randomText( const char* file )
{srand(clock());wchar_t* text=new wchar_t[MAX_TEXT_LEN];wchar_t** textp=new wchar_t*[MAX_TEXT_LEN];for (int i=0;i<MAX_TEXT_LEN;i++){textp[i]=text+i;}//
    memset(text,0,MAX_TEXT_LEN*sizeof(wchar_t));setlocale(LC_ALL,"chs");FILE* f=fopen(file,"r");wchar_t *curPos=text;int len=0;while(fgetws(curPos,1000,f)){len+=wcslen(curPos);curPos=text+len;}printf("长度:%d\n",len);std::sort(textp,textp+len,[](wchar_t* p1,wchar_t* p2){return wcscmp(p1,p2)<0;});int nMaxCmp=0;wchar_t* pMax=text;for (int i=0;i<len-FOWWARD+1;i++){int tmp=getMaxCmp(textp[i],textp[i+1]);if (tmp>nMaxCmp){pMax=textp[i];nMaxCmp=tmp;}}wprintf(L"%d\n",nMaxCmp);wstring st(pMax,pMax+nMaxCmp);int maxLength=2000;wchar_t* randStr=new wchar_t[maxLength+1];randStr[maxLength]=L'\0';randStr[0]=L'始';randStr[1]=L'皇';for(int i=0;i<maxLength-FORWARD_LEN+1;i++){int l=0;int r=len-1;int re=-1;//搜索结果iwhile(1){if(l==r){if(wordCmp(randStr+i,textp[l])==0)re=l;break;}             int m=(l+r)/2;if(wordCmp(randStr+i,textp[m])<=0)r=m;else l=m+1;}wchar_t tmp=L' ';int j=1;while(re!=-1&&re<len&&wordCmp(textp[re],randStr+i)==0){if(rand()%j==0&&textp[re][FORWARD_LEN-1]!=L' '&&textp[re][FORWARD_LEN-1]!=L'\n')tmp=textp[re][FORWARD_LEN-1];re++;j++;}if(tmp==L'\0')tmp=L' ';randStr[i+FORWARD_LEN-1]=tmp;         }wprintf(L"%s\n",randStr);return L"";
}

由于有太多空格和换行,我把很多空格和换行干掉了,生成的文本:

始五年，淮阴侯，左右既行阴事。而李夫人田荣如此始汤方；使安曰“我”少季札书相楚、
蔡之间行四年，夹持其後宫中，又 当见臣之。 燕、卫子曰：“赵王欲发兵尽也。秦来，
五色。反，而句戟百越王。舜。”臣，奸神可得全乎南阳，乃为太阿房君臣，功。数破灭之
宗庙，岂非真草美之意方仙神或朝，秦始。韩宣公十七年徙者务在人安邑，秦灭赵又可以为
长美女极人。风居下相攻。 灵王其次曰“道备燕饮，所置吏为沛，而能督亢竖子欣喜
。先据地？”市，带复予金作，而何如廷也。项王遂以为於兹兹益矣，是相国有作奸乃与宋
元年，颇用文德，杭，此时极亡之少傅其言也，以天五年，遂西伯阳人。”诸吕礼之，遇之
後去学者少与其子不享诸臣征巴蜀，海内其察礻必祸及八·伍子章章，无书 太守。陈，还
报劳者不胜 於边邑，问所以收下。”公子曰：“秦，高之，莫敢举有济北地。故国者年
伐吴东王信武王基者夫，破镜；离为王耳目不朝。简子将兵十年卒。 

把FORWARD_LEN改成3,保留换行符:

始皇自以为九卿尽会立，是必大矣，不疑。荀息。斡流而下报赵王以诸侯，食顷，齐桓，将
不能守也。
韩厥，厥称太子，子文王生曰：
平原君求救，其将欲移兵而去。弃女子长为陶天下服。
王者之无尽索之时，季文子奔莒，则蛮夷所侵暴乱，畏诛，死者不求何获！我真王嗣，
冠固何当？”曰：“为此药者乃‘刘’也。
汤征诸侯，昭公卒，子庄王曰：“始上数在困急之中。
太史公遭李陵既壮，杀
厉公於朝廷。
清明风居西北外国。

把FORWARD_LEN改成4:

始皇帝。其语在吕后语中。于丞相去，王乃反诛我。嗟乎，利诚乱之始也！夫秦王有连。其
居於秦，
莫如从亲以孤秦。大王命季历，明天人分际，通古今之义，则两失
之矣，
其势必不
来。至长安。
武帝立，以微眇之身，国治兵︹，可以备胡。数月而降，杀之。使弃疾为陈公，不随项
羽，故立为殷王，都朝歌。诸侯兵罢归，乃阴聚徒党及谋反者。
大馀三十二年，周致伯於秦孝公、楚悼王、越王，与城阳、琅邪负海之国
也。此
两人深相结，请案兵无攻。愿大王资馀兵，击楚，其意不厌。今秦之欲伐楚，败而亡王舟。
光惧，袭楚至邓。楚兵惧，自秦归。而楚太子商臣弑其父成王代立。帝廑崩，立沃
甲兄祖辛之子祖丁，是为缪侯，续绛侯後。十二年，彗星见

已经有点史记样子了,把FORWARD_LEN改成10的时候,由于没有这么长的重复子串,直接输出实际原文了,汗

转载于:.html