代码中的“顶针”

关于顶针

顶针，亦称顶真、联珠、蝉联，是一种文学修辞方法，是指上句的结尾与下句的开头使用相同的字或词，用以修饰两句子的声韵的方法。需要注意的是，使用这个方式时，毋须限制上下句的字数或平仄，但上下句交接点一定要使用相同的字或词。

例如：

“归来见天子，天子坐明堂。”——《木兰辞》
“军书十二卷，卷卷有爷名。” ——《木兰辞》
“忽闻海上有仙山，山在虚无缥缈间。” ——《长恨歌》

——摘自百度百科

那么，一般地，我们可以认为，一段文本的后某几个字符和下一段文本的前几个字符相等，则构成顶针。这个定义不再限制于中文。
例如：

1.They’re all terrible , except this one.

此处逗号前的e和逗号后的e构成了顶针。

如果是多个字符，比如还有：

2.manegement , mental.

我们直观地能发现ment是顶针的部分。
那么问题来了：如何让机器发现是否有顶针结构存在呢？

一个最简单原始的想法是，检查上一个串最后一个字符和下一个串最前面一个字符。 可是，在遇到第二个例子时，这种方法显然不起作用了。

我们不妨通过一个题目来认识顶针的判断。

一个编程题

那一天，一个阳光明媚的午后，远在武汉的高中同学发来消息：
“看看F题.”
我说：
“怎么回事？”
给我发来一份pdf。
我一看，哦，原来是去年他们武汉大学，有一个新生赛，一共一百多号人参赛。
紧接着我看了看题面，
他说要我试试，
我说可以。
（doge）

题面

思考

对于这个题目本身，因为需要处理的输入种类并不多，无非十种，是可以全部用特殊情况实现的，而不需要什么算法.
以下是C++直接实现：

#include <iostream>
using namespace std;
int main()
{int n = 0;cin >> n;char ch[21];cin >> ch;for(int i = 0; i < n; ++i){switch(ch[i]){case 'A':{if(i != 0 && (ch[i - 1] == 'C' || ch[i - 1] == 'F'))cout << "rand";elsecout << "grand";break;}case 'B':{if(i != 0 && ch[i - 1] == 'H')cout << "olorful";elsecout << "colorful";break;}case 'C':{cout << "amazing";break;}case 'D':{if(i != 0 && ch[i - 1] == 'A')cout << "elicate";elsecout << "delicate";break;}case 'E':{if(i != 0 && ch[i - 1] == 'H')cout << "alm";elsecout << "calm";break;}case 'F':{if(i != 0 && (ch[i - 1] == 'J' || ch[i - 1] == 'D'))cout << "nchanting";elsecout <<"enchanting";break;}case 'G':{if(i != 0){if(ch[i - 1] == 'J')cout << "gendary";else if(ch[i - 1] == 'B' || ch[i - 1] == 'I')cout << "egendary";elsecout << "legendary";break;}}case 'H':{cout << "fantastic";break;}case 'I':{cout << "beautiful";break;}case 'J':{cout << "terrible";break;}}}return 0;
}

但是！

如果我们用通法去做这个题呢？

再看一看题，我们不难发现，所谓的仓鼠语，不就是在产生“顶针”时去掉重复部分吗？
如何去掉重复部分？
这成了我们用通法解题的一个瓶颈.
于是，我们回到了#关于顶针#栏目里的问题：

如何让机器检查是否有顶针存在？
这一个编程题里，有一个顶针结构是和其他顶针不太相同的：

terrible，legendary

在删除重复部分后，它们在“仓鼠语”中应该写作“terriblegendary”.

我们不妨试试这样的做法：

将两个单词对齐.

对于所有对齐的部分，从第一个字符开始检查是否全部相等.
这里需要检查的是“terrible”和“legendar”.显然不等.
既然不等，将下一个串（legendary）右移一位，即

再次检查对齐部分“errible”和“legenda”…还是不等.
我们重复这样的操作6次后，发现：

此时对齐部分为“le"，相等了.
那么，我们只需要将对齐部分之后的文本输出就可以了.
怎么用代码实现？
首先我们要将对齐的过程算法化：

在这之前要说的是，C/C++中任何数组的第一个元素的下标都是0.所以下面的叙述也符合这个规则啦

1.现有2个字符串，一个在前，一个在后.获取前一个字符串的长度为len.
将两个字符串“一一对齐”.这一步其实是没有实际操作的，而是在得出算法的过程中在我们的脑海中想象的~

2.定义一个数 j，初始化为0.将 j 表示第二个字符串的第一个字符所对齐的第一个字符串的字符的下标.
有点绕？不妨看一看这个例子：
例如，terrible和legendary对齐：
下一个串“legendary”的第0位 ‘l’ 和上一个串“terrible”的第4位 ‘i’ 对齐，那么j应该就是4了.
另外， len-j 自然也就可以用来表示目前两个串对齐的字符个数了.

3.检查对齐的部分，即检查前一个字符串的第 j 位至最后一位 是否分别和下一个串的第0位至第 len - j 位分别相等.

4.如果对齐的部分不全相等，则应该令 j 增加1.

5.重复步骤3~4.直到遇到对齐的部分相等的情况.

6.结束，输出一个整数len - j .

7.利用这个 len - j ，我们在上一个串的后面输出下一个串的第 len - j 个字符至最后一个字符，就成功地打印了去掉顶针的文本，即翻译成了“仓鼠语”.

如果还是有点难理解，可以自己打一打像我上面图片那样的草稿，我也是这样得出结论的~

以下是C/C++的代码（注释用了C++式，无所谓啦）

int check(char src[] , char next[])
/*src为上一个串，next为下一个串.
这里都用了字符数组.*/
{int j = 0;int len = strlen(src);/*定义len1为上一个串的长度.*///先将前面的输出串与被检查的串一一对齐.//j每加1，被检查的串就往右移动一次.这时对齐的字符个数应该为len1-j，//src中对齐的部分第一个下标应该是j（数组的下标从0开始）for(; j < len; ++j){//检查目前对齐的是否全部相等bool Equal = 1;for(int m = j , i = 0; m < len; m++ , i++){if(src[m] != next[i]){Equal = 0;break;}}if(Equal)//如果对齐的都相等了，对齐的这部分应当作为后缀./*因此，我们退出外面的这个for循环，执行下面的return语句，返回len - j.*/{break;}}return len - j;//返回对齐个数.
}

有了这个函数，我们就能愉快地进行“仓鼠语”的翻译了~

可以发现，这个函数在看上去最简单的“只有上一串最后一个字母和下一串第一个字母构成顶针”的情况下，反而运行时间最长——他需要循环到 len - j = 1时，也就是要对 j 做 len - 1 次加法，并且每次加法前都要检查 len - j 个位置是否相等. 因此其复杂度上限是O(nlogn). 当然了，下限是O(1).
（可是谁会写两个相同的单词/句子做顶针啊喂！）

这里贴出F题C++题解：

#include <iostream>
#include <cstring>
using namespace std;int check(char src[] , char next[])
/*src为上一个串，next为下一个串.
这里都用了字符数组.*/
{int j = 0;int len = strlen(src);/*定义len1为上一个串的长度.*///先将前面的输出串与被检查的串一一对齐.//j每加1，被检查的串就往右移动一次.这时对齐的字符个数应该为len1-j，//src中对齐的部分第一个下标应该是j（数组的下标从0开始）for(; j < len; ++j){//检查目前对齐的是否全部相等bool Equal = 1;for(int m = j , i = 0; m < len; m++ , i++){if(src[m] != next[i]){Equal = 0;break;}}if(Equal)//如果对齐的都相等了，对齐的这部分应当作为后缀./*因此，我们退出外面的这个for循环，执行下面的return语句，返回len - j.*/{break;}}return len - j;//返回对齐个数.
}
}int main()
{int n = 0;cin >> n;char s[15] = {""};char a[15] = {"grand"};char b[15] = {"colorful"};char C[15] = {"amazing"};char d[15] = {"delicate"};char e[15] = {"calm"};char f[15] = {"enchanting"};char g[15] = {"legendary"};char h[15] = {"fantastic"};char I[15] = {"beautiful"};char j[15] = {"terrible"};for(int i = -1; i < n; ++i){char c;c = getchar();switch (c){case 'A':{if(i == 0){strcpy(s , a);printf("%s" , s);}else{int start = check(s , a);strcpy(s , a);int p = start;//从[对齐个数]这个位置开始输出，前面[对齐个数]个元素不输出.while(a[p] != '\0'){cout << a[p];p++;}}break;}case 'B':{if(i == 0){strcpy(s , b);printf("%s" , s);}else{int start = check(s , b);strcpy(s , b);int p = start;while(b[p] != '\0'){cout << b[p];p++;}}break;}case 'C':{if(i == 0){strcpy(s , C);printf("%s" , s);}else{int start = check(s , C);strcpy(s , C);int p = start;while(C[p] != '\0'){cout << C[p];p++;}}break;}case 'D':{if(i == 0){strcpy(s , d);printf("%s" , s);}else{int start = check(s , d);strcpy(s , d);int p = start;while(d[p] != '\0'){cout << d[p];p++;}}break;}case 'E':{if(i == 0){strcpy(s , e);printf("%s" , s);}else{int start = check(s , e);strcpy(s , e);int p = start;while(e[p] != '\0'){cout << e[p];p++;}}break;}case 'F':{if(i == 0){strcpy(s , f);printf("%s" , s);}else{int start = check(s , f);strcpy(s , f);int p = start;while(f[p] != '\0'){cout << f[p];p++;}}break;}case 'G':{if(i == 0){strcpy(s , g);printf("%s" , s);}else{int start = check(s , g);strcpy(s , g);int p = start;while(g[p] != '\0'){cout << g[p];p++;}}break;}case 'H':{if(i == 0){strcpy(s , h);printf("%s" , s);}else{int start = check(s , h);strcpy(s , h);int p = start;while(h[p] != '\0'){cout << h[p];p++;}}break;}case 'I':{if(i == 0){strcpy(s , I);printf("%s" , s);}else{int start = check(s , I);strcpy(s , I);int p = start;while(I[p] != '\0'){cout << I[p];p++;}}break;}case 'J':{if(i == 0){strcpy(s , j);printf("%s" , s);}else{int start = check(s , j);strcpy(s , j);int p = start;while(j[p] != '\0'){cout << j[p];p++;}}break;}}}return 0;
}

嗯…或许代码有些地方还是不够简洁，写了200多行…
蛤？你要在考场上用这种方法解F题？
tql.（该简单就简单嘛，之前的直接实现挺好的）

拓展

发现了F题的通解后，在景点多起来的时候，我们的方法可就比直接列举所有情况简单多了~（当然，复杂度上咱不敢比，check函数已经是O(n²)复杂度了，而列举、打表可是O(1).列举过是能过，但是情况比F题更多时，谁又能保证自己的手速跟的上呢？

从这个题发散，留一道题给各位读者（嘶，应该没人看吧）：

输入一段英文文本，检查其中顶针单词对的个数（两个相邻单词完全一样时不算）

只需要对check函数稍加修改，如果在 j = 0时，对齐的部分就全相等了，并且前一个串和后一个串的长度也是相等的， 那么就返回0而不是 len - j.这样就避免在输入两个相同的单词时也检查为顶针结构了~

总结：ACM的日子，是十分需要交流讨论，拓展思考的~