Dai Chao

fordring866@gmail.com | Put your faith in the Light!

简单的字符串练习1

初次尝试刷题,当然要刷简单的啦。

Root :: Competitive Programming 3: The New Lower Bound of Programming Contests (Steven & Felix Halim) :: String Processing :: String Matching :: Standard

455 - Periodic Strings

问题描述:求一个字符串的最小周期,例如”123123123”的最小周期为3。从数据规模来看,穷举法完全可行,但还是要学习一下这位老哥对KMP的巧妙运用:

设字符串A长度为s,求出整个字符串的最大border长度t。如果s-t | s,那么最小周期为s-t;否则,最小周期为s。

证明:如果s-t | s,那么A可以分为若干个长度为s-t的部分,叫做A1, A2, …, An。 最长border作为前缀时为A[1…n-1],作为后缀时为A[2…n]。 因此,A1 = A2 = … = An,最小周期长度为s-t。

886 - Named Extension Dialing

问题描述:给一堆英文名字,都由两个单词组成,每个名字都有唯一的4位编号,例如Tirion Fordring 0303。现在有一个用户拿手机拨号,按照九键输入的方式拨出了若干个号码,问对于每个号码,有哪些名字能与之匹配,输出其编号。匹配的规则是,如果号码与某个编号一致,则成为唯一匹配并忽略其他匹配,否则寻找满足”the first letter of the first name followed by the first letters of the last name”的名字,例如8367对应”T For”,输出0303。

这本来是一道比较简单的题目。

构造Trie树的复杂度为last name的长度和,查找匹配的复杂度为号码的长度和。

然而我TM看错题了!!!

我把匹配条件看成了”the first letters of the first name followed by the first letters of the last name”。

于是在我眼里,这道题问的是,已知字符串A,B,P,请问P能否由A和B的各一个前缀组成。

我甚至把它做了出来,简要描述一下方法:求A与P的最长公共前缀长度lcp,再求B+P的前缀函数pf,从而求出B+P的最长、又不长于P的border(设长度为bd)。若len(P)-bd小于lcp,说明P长为bd的后缀是B的前缀,而剩下的前缀长度小于lcp,因此是A的前缀。

10298 - Power Strings

问题描述:和455完全一样,除了输入输出的要求。

由于UVa不给用户看自己交的代码,因此这道题之前的代码全都丢了。后面的题目解答我会保存下来,留作纪念。

11362 - Phone List

问题描述:给一堆字符串,问是否存在某个字符串是另一个的前缀。

用Trie树依次插入。如果路过叶子结点,或插入最后一个字符时没有新建结点,则答案为是,此后的所有输入可以不做处理。

11475 - Extend to Palindrome

问题描述:给一个字符串,往后面加最少的字符,使其成为回文串。

首先学习一下Manacher算法。该算法输入一个字符串s,输出两个数组d1和d2,d1[i]代表以s[i]为中心的奇数回文子串个数(包含s[i]自己),d2[i]代表以s[i]为中心的偶数回文子串个数。

int d1[n],d2[n];
// 奇数长度,中心唯一
for(int i=0,l=0,r=-1; i<n; i++) {
	// k表示现在已知有几个以i为中心的回文子串
	// 若i>r,不能利用边界内部的信息,因此k=1(中心本身)
	// 否则,取 对称位置的d1值 与 中心到边界右侧的距离 的较小值
	int k=(i>r)?1:min(d1[l+r-i],r-i); // r-i+1?
	// 简单算法,将k增加为正确的d1值
	// 每次都试图找到第k+1个回文子串,因此比较s[i-k]与s[i+k]
	while(0<=i-k && i+k<n && s[i-k]==s[i+k]) k++;
	// 赋值后,k需要减1,迎合下一步更新边界的计算
	d1[i]=k--;
	// 现在,以i为中心的最长子串为[i-k,j+k]
	// 判断一下是不是需要更新一下边界
	if(i+k>r) {l=i-k;r=i+k;}
}
// 偶数长度,规定中心处于偏右的位置
for(int i=0,l=0,r=-1; i<n; i++) {
	// 中心本身还需要和自己左邻居比较,因此k最小为0(一个都不能跳过)
	// 与对称回文子串的中心,应该是i的对称点的右邻居,因此是d2[l+r-i+1]
	int k=(i>r)?0:min(d2[l+r-i+1],r-i+1);
	while(0<=i-k-1 && i+k<n && s[i-k-1]==s[i+k]) k++;
	d2[i]=k--;
	if(i+k>r) {l=i-k-1;r=i+k;}
}

现在来看这道题就非常简单了:在Manacher算法的过程中,每次更新边界时都检查r==s.length()-1。如果是,则可以终止循环,将此数组用到的l记录为x1和x2(有两个数组需要计算,初始值应该都是s.length()-1,代表最多从末尾添加起)。取x1和x2的较小值记为x,然后依次向字符串添加s[x-1]到s[0]的字符。

11576 - Scrolling Sign

问题描述:按顺序输入N个长度为len的小字符串,求最短的字符串S,使得这些小字符串都是S的子串,且第一次出现的位置不随着输入顺序递减。输出这个字符串的长度。(例如,ABCD/DEFG/DEFG/GGGG可以合并为ABCDEFGGGG)

我的方法:开足够大的字符数组,反向输入小字符串,两两之间插入’$’。从输入第二个字符串起,求当前位置开始、长度为2*len+1的子串,也就是str[i+1]+'$'+str[i]的border。这样就求出了前一个小字符串的后缀最多有多长,可以作为后一个小字符串的前缀。把这些求出的长度从N*len中减去,就得出了结果。

12467 - Secret Word

问题描述:给一个字符串S,要求找出最长的子串,使其倒置为S的某个前缀。

方法:构造字符串S+'$'+S2,其中S2为S的倒置,计算其前缀函数。在计算过程中,从S2起,记录出现的最大函数值maxbd及当前位置i。求出i的对称点mark = len-i-1,那么从该点开始、长度为maxbd的子串,就是要输出的结果。

11888 - Abnormal 89’s

问题描述:给一个字符串,判断它能不能由两个长度至少为2的回文串组成。如果不能,判断它是不是回文串。

。。。。。。

明天就开始上班了,有空补上。

总而言之,迈出了摆脱算法废柴的第一步,还是挺开心的,希望以后能继续进步。

提交记录