读蒋方舟《给清华大学的一封信》

作者蒋方舟最想要表达的就是对学校不满,对学校的学生不满。清华是人们公认的大陆工科顶级学校,相比之下,北邮的学生有什么见解似乎都不会有太多的影响力。然而,事实上却是,人们是否去思考与他所在的学校无关,人们是否拥有最基本的素养与考试成绩无关(不是逆相关,我没有贬低成绩好的同学的意思)。

大学乃修学之地,这里人物形形色色,人各有志,不想专心学术也无妨,只是纳税人的钱可能会尽不到作用而已。然而,当这种思想成为大学里的主流思想时,问题就变得可怕了。如果一个人没有一个目标的话,这个人一定是没法真正去学习一些东西的。又因为我所遇到的北邮的大多数老师不是念课本就是读ppt,与我在中学时幻想的大学课堂大相径庭,甚至还要更古板。而大多数学生的想法也只是不挂科,为了好成绩的人似乎也只是为了那些好成绩能带来的东西,根本不在乎是否真正理解了老师所讲的内容,是否真的学会了这些知识。更重要的问题则是作为判断学生是否学到知识的考试也是对这些人有利的。这样的恶性循环体现出来就是:

A:“这块为啥这样做啊?”

B:“你不用管,背结论就行”

再接下来A有两种可能,一种是自己纠结着或者说服别人跟他一起纠结,并最终找到答案;另一种则是被其他人同化,最终失去真正求知的心。这只是一个简单的例子,但却很可能是问题的核心:当我们想去思考的时候,周围的人在阻碍我们思考。不去思考,怎么可能称得上是学术,怎么可能最后得出真正的学术成果?上面例子的延续就是等我们大学毕业后,更多的人想的不是如何用知识去创造财富,而是如何用所谓的世故来“混”社会。并且这些人把自己的世故当作成熟,把别人的思考当作幼稚。

上面只是一个简单的例子,不过不管怎么样,殊途同归,大多数人都会被同化,并成为体制的维护者。我们这个年龄的人大多数都会抱怨现在这个社会,但没有任何人有勇气去改变这个社会,包括我自己。就像蒋方舟文章里面说的那样,如果是既得利益者,尽力去维护自己已经得到的利益也就罢了,问题是还有许多利益被剥夺的人,他们竟然也会去维护这种体制,让自己曾经的悲剧延续下去,嘴里还振振有词:“反抗是没有意义的”。是啊,这些人即使真的去反抗又有什么意义,因为即使这些人反抗成功了,社会到最后也还是这个样子。甚至在我们学生群体里,这样的人也很常见:嘴里骂着政府,却整天梦想着能不劳而获得到公务员的职务。嘴里骂着贪官,心中却在意淫着当上了贪官怎么能贪到更多的钱。包括我自己,都应该问自己这样一个问题,如果我是统治者,我能不顾那些贪官的反对,真正地维护公民的利益吗?我是公民的话,我又能保证为了自己的利益而尽力不去损害他人的利益吗?

最后说一下那个《盛世》这本书,说实话看完之后真的觉得很震惊,但文中所写却又似乎就是我们身边正在发生的事实。文中的那段“他们不这么想就更可怕了”,说的就是中国人自古以来就有的双重思想。我们所接受的教育,从小就教我们作假,似乎没有双重思想的人反而是社会的异类,一面骂着别人,一面又奉承着别人;最后的结果也只能是不自然地维护着这个体系。不过,如果这真的像《1984》里面的双重思想倒还好,至少他们思考了并且得出了自己的结论,不管正确与否,总比《1984》里面的反乌托邦真正期望的让人不去思考要强。

ps:这个只是马哲的作业,说实话我还是喜欢打字而不是写字,可惜如果我真的打印出来,老师一定会认为我是从网上摘抄的吧。不过话说回来,这个老师敢于这么留作业我就已经很钦佩了。大学生如果都能有像李刚老师那样的基础知识的话,不管他们得到的结论如何,总比现在要强。(这段话不会出现在手写版本里)

ps2:好久没有写这类文章了,不过这次自己还算满意。

KMP的科普文章: 为什么KMP提高了效率

2021.09.26 补充:原文在 2011年10月31日发表在之前的 Blog 上,本文是基于 Internet Archive 上面的记录手动迁移过来的内容。

以下为正文:

本文原创,转载请注明出处: http://atarss.com/blog/?p=193

计科无能者无视第一段,着急写作业的建议不用看第三部分,直接用第二段的方法。

KMP的实质是自动机匹配的优化,即不需要构造自动机,而通过模式字符串的自我匹配来简化过程,使预处理的时间复杂度降为O(m)。

1.字符串匹配的过程;以及为什么我们能优化算法

假设要被搜索的字符串是”bacbababaabcbab”,要搜索”ababaca”这个串。

浅绿色的表示已经被匹配的字符,我们定义正在被匹配的长字符串里面的位置是i=5,要搜索的模式串已经匹配到j=6第6个字符而且与原始的字符串不匹配。按照朴素的匹配算法,我们应该让i++,即从i=6开始匹配。但是我们已经知道i从5~9与B串的j=1~5是完全相同的。因此即使我们不知道A串的内容,只通过B串的内容以及我们已经匹配到第6个字符这两项数据,就可以知道从i的下一项数据一定是不匹配的。

同理我们知道主串在i=7时的匹配可能是成功的,因此我们可以设计算法不去匹配i=6时的情况而直接跳到i=7去匹配,而且右移2位这个数字2只是通过B串(要搜索的串)的自我匹配来完成的,也就是可以在匹配前完成计算。而这就是KMP较朴素匹配算法的优化之处。

2.如何计算当不匹配时主串要移动多少位

依旧要搜索这个串”ababaca”,我们已经知道要跳过多少个字符的字符数量是与要搜索的字符串(A串)无关的,实质是要搜索的串(B串)的自我匹配。而这个信息可以被预先计算出来并被存储起来。

每次偏移多少位显然与匹配到B串第几个字符时开始不匹配的j位置有关,因此我们定义一个数组来存储这个偏移量的信息,定义为D[1..t],t为B串的长度,下标从1开始。

※我们前提假设,每个字符只能读取一次,真正的字符指针不能后退。

实质即为,假设当匹配到j=n时不匹配,即j从1~(n-1)都是匹配的,那么偏移量就是字符串从后向前自我匹配时到达前面之前所能达到的最大的位置。举例:

按找从下往上看的顺序就能找到偏移量,显然最长的匹配的偏移量为2。按照这种方法就能找到所有的偏移数组的值。

若j=1时不匹配,毫无悬念,偏移量为1,;
若j=2时不匹配,则右移一位也没有意义,直接右移两位,偏移量为2;
若j=3时不匹配,i=3与j=1时相同,因此偏移量为3-1=2;

若j=4时不匹配,同理得偏移量为2;
j=5时上面已经分析过,偏移量为5-3=2;
j=6时,同理,偏移量为6;
j=7时,偏移量为7-1=6;

在计算的过程中,我们知道,真正找到的并不是偏移量,而是最长真字串的长度。我们成这个关于j的数组(函数)为前缀函数Pi[j]。

3.前缀函数的递推计算

根据上面的算法,我们同时得到前缀函数的值

下面说明递推的过程:
假设我们已经知道了j=1~4时Pi[j]的值了,如何推得Pi[5]和Pi[6]呢?

Pi[4]=2,说明字符串B[1..2]与B[3..4]相同,又B[5]==B[3],所以,P[5]=P[4]+1=3;

而Pi[6]却不等于Pi[5]+1,这是因为B[4]≠B[6],因此没法通过Pi[5]+1得到Pi[3],但同时,B[1],B[3],B[5]均为字符’a’,或许还可能通过Pi[3]或Pi[1]得到Pi[6],但一次次匹配都发现B[6]不等于B[4]且B[6]不等于B[2],这时,Pi[6]只能是0。

抽象一下,就得到Pi[j]的算法:
先用一个临时变量T=Pi[j-1]
若B[T] == B[j],那么Pi[j] = Pi[j-1]
否则,T=Pi[T],继续上面的操作,直到Pi[T] == 0,这时Pi[j]=0。

最后附上计算Pi[6]的示意图:

最后一部分参考了M67的文章,在此对其表示感谢。

http://www.matrix67.com/blog/archives/115