一个字符串拼接的算法问题

发布时间:2016-12-7 16:43:45 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"一个字符串拼接的算法问题",主要涉及到一个字符串拼接的算法问题方面的内容,对于一个字符串拼接的算法问题感兴趣的同学可以参考一下。

一、相关定义。         在讨论算法之前,为了便于理解,先给出如下定义:         1、序列:两端非空字符的字符串称为序列S。         2、元序列:无空字符的序列称为元序列M。         3、子元序列:序列S中的空格将序列分割成若干个元序列,每个元序列称为序列S的子元序列。假设S有n个子元序列,则S可表示为:M1_M2_..._Mn。         4、序列长度:序列S中的字符个数称为序列S的字符长度,记为L(S)。序列S中的子元序列个数称为序列S的元长度,记为L'(S)。         5、序列连接:序列S1与序列S2连接,是指S2直接加在S1之后组成一个长序列S,记为:S=S1S2。显然,L(S)=L(S1)+L(S2),L'(S)=L'(S1)+L'(S2)-1。         6、序列乘接:序列S1与序列S2乘接,是指序列S1中的子元序列与序列S2中的子元序列两两连接后,再用空格相互连接起来组成一个长序列S。记为S=S1XS2,显然L'(S)=L'(S1)XL'(S2)。下图演示的是L'(S1)=3,L'(S2)=2时,S1XS2的过程。          二、问题定义。         有两个序列S1、S2,其中,L(S1)=i,L(S2)=j,L'(S1)=m,L'(S2)=n。求L(S1XS2)。 三、推导过程。         一开始,我认为L(S1XS2)是一个变值,但存在一个上限。经过推导,发现L(S1XS2)是一个常量。假设S1中第p个子元序列的长度为Xp,S2中的第p个子元序列的长度为Yp,则有:          综上所述,L(S1XS2)是一个常量,且等于n*i+m*j+m+n-m*n-1。 四、应用:         在本人博客《汉字转拼音c/c++源码,支持gb2312和utf8 》中,若中文字符串在转换时,需要支持多音字,则需要知道序列乘连的字符长度,以防数组越界,造成程序崩溃。         

上一篇:Linux 套接字编程中的 5 个隐患
下一篇:Hash表题目整数hash-HDOJ1425(转载)

相关文章

相关评论