口头禅

来自计算思维百科
跳转至: 导航搜索
口头禅.jpg

口头禅往往会降低一个人话语的可信度。为了改掉口头禅,郑博士利用自动分析程序对他发表过的演讲和讲课内容进行了语音识别,并进行了归纳总结。总结中,出现3次以上的字符串会被视为“口头禅”。郑博士想要从一段演讲内容“urhiurhowareyouur”中找出长度最长的口头禅,然后最先改掉这个口头禅。

解决方案

要帮郑博士找出长度最长的口头禅,我们先要找出口头禅,再找其中最长的口头禅。

方案一:蛮力法

我们事先并不知道哪些是口头禅,只要是出现3次以上的字符串都是口头禅。所以我们要找出字符串urhiurhowareyouur中出现3次以上的子字符串。再从这些字符串中选出长度最长的一串就是郑博士需要改的第一句口头禅。由于任意子字符串都有可能是口头禅,那么我们要将所有的子字符串“u”“ur”“urh”等一一与演讲内容“urhiurhowareyouur”进行匹配,计算出现次数。这个工作量巨大。必然存在更加简便的方法。

运用的计算思维

蛮力法是从我们正常的思维方式中衍生出来的最直接的解决问题的方法。但是从上述分析过程来看,蛮力法解决问题所需要的时间长,对于规模小的问题比较适合。

方案二:后缀数组法

后缀数组是以字典顺序排列某个字符串的所有后缀。例如“apple”的后缀数组为:

序号

后缀起始位置

后缀字符串

0

0

apple

1

4

e

2

3

le

3

2

ple

4

1

pple

其中,apple这个后缀在apple这个字符串中处在第0个位置,e这个后缀在apple这个字符串中处在第4个位置,le这个后缀在apple这个字符串中处在第3个位置,依次类推。。。

那么,我们可以求出字符串urhiurhowareyour的后缀数组如下:

序号

后缀起始位置

后缀字符串

0

9

areyouur

1

11

eyouur

2

6

howareyouur

3

2

hiurhowareyouur

4

3

iurhowareyouur

5

13

ouur

6

7

owareyouur

7

15

r

8

10

reyouur

9

5

rhowareyouur

10

1

rhiurhowareyouur

11

14

ur

12

4

urhowareyour

13

0

urhiurhowareyour

14

8

wareyour

15

12

your

我们找的口头禅要在字符串urhiurhowareyouur出现3次以上,也就是说口头禅肯定至少是3个后缀的前缀。并且这些后缀在后缀数组中相邻。根据这个规律,我们就能将问题转变成“求所有后缀数组中任意连续3个后缀中最长的共同前缀”。

因此我们可以找出两组,一组是第7~10行中的共同前缀“r”,另一组是第11~13行的共同前缀“ur”。所以,演讲内容中最长的口头禅是“ur”。

运用的计算思维

方案二首先对初始字符串进行预处理,虽然“后缀数组”占用了较大空间,但是节省了后续求解的时间,是一种“以空间换时间”的策略。我们从后缀数组中发现了口头禅与后缀前缀关系的规律,并且运用规律将问题转化成另一个等价的问题,找到了口头禅,运用的是“学习”和“启发式”的计算思维。

参考文献

[1]具宗万.算法问题实战策略[M].崔盛一,译.北京:人民邮电出版社,2015