[算法]关于字符串的算法

判断字符串的匹配(一个字符串是否在另一个字符串中出现):
KMP, 时间复杂度 线性, O(n)


找出k个字符串的最长公共子字符串(每个字符串长度不超过n):
使用suffix tree. 对于每个字符串建立一棵suffix tree的时间是线性O(n),合并这k棵suffix tree, 然后寻找合并过的大树中拥有属于所有string的最深的节点.


两个文件,各自拥有很多单词.寻找在两个文件中重复出现的单词:
可以用feed-forward bloom filter

[算法]拳皇友谊赛

这两天看到的一道蛮好玩的题：
变态的比赛规则：为了促进各部门员工的交流，百度(baidu)举办了一场全公司范围内的"拳皇友谊赛"，负责组织这场比赛的是百度的超级"拳皇"迷W.Z. W.Z不想用传统的淘汰赛或者循环赛的方式，而是自己制定了一个比赛规则。

由于一些员工（比如同部门或者相临部门员工）平时接触的机会比较多，为了促进不同部门之间的交流，W.Z希望员工自己组成不同组。不同组之间的每两个人都会进行一场友谊赛而同一组内的人则之间不会打任何比赛。

比如4个人，编号为1--4,如果分为两个组并且1,2一个组，3，4一个组，那么一共需要打四场比赛：1 vs 3,1 vs 4,2 vs 3,2 vs 4. 而如果是1,2,3一组，4单独一组，那么一共需要打三场比赛: 1 vs 4,2 vs 4,3 vs 4.

很快W.Z意识到，这样的比赛规则可能会让比赛的场数非常多。W.Z想知道如果有N个人,通过上面这种比赛规则，总比赛场数有可能为K场吗？比如3个人，如果只分到一组则不需要比赛，如果分到两组则需要2场比赛,如果分为三组则需要3场比赛。但是无论怎么分都不可能只需要1场比赛。

相信作为编程高手的你一定知道该怎么回答这个问题了吧？ 那么现在请你帮助W.Z吧。

输入
每行为一组数据，包含两个数字 N, K

输出
对输入的N,K 如果N个员工通过一定的分组方式可能会一共需要K场比赛，则输出"YES",否则
输出"NO",每组数据占一行。所有的输入输出均为标准输入输出。

SOL:这道题是一道潜伏很深的动态规划。先建一下模：N个人，如果分成m组，每组x_i人，那么需要打的比赛场数是

\sum_{i\neq j} x_ix_j

。所以本题就是给定N,看是否能找到一个组人数划分使得上式等于K。

做一下变化:

K=\sum_{i\neq j} x_ix_j = \frac{(x_1+\ldots+x_m)^2-\sum_ix_i^2}{2}=\frac{N^2-\sum_ix_i^2}{2}

所以这里我们把这道题变成了如何找到m个数使得这m个数的和等于N，平方和等于N^2-2K。

令T(s)为所有"平方和为s的一组数的和"的集合，即:

T(s)=\{x_1+\dots+x_m|\forall \sum_ix^2_i=s\}

所以T(5)={3,5}，也就是说5可以分解为1+1+1+1+1也可以分解为1+2^2。
关于T(s)的递推式为

T(s)=\left\{\begin{array}{ll}
(\bigcup_{i=1}^{s/2} (\{t\} \cup T(i))\odot T(s-i)) & i=t^2\\
\bigcup_{i=1}^{s/2} T(i)\odot T(s-i) & \textrm{otherwise}
\end{array}
\right.

这里定义

A\odot B = \{ a+b | \forall a\in A, b\in B\}

边界条件: T(1)={1}

[算法]找树的重心

以前算法课作业做过这道题。今天在网上又碰到了。

给一个有n个结点的树，每个节点i都有一个正权重w(i),每条边j也有一个正权重c(j). 要求给出一个线性复杂度的算法，找出一个结点u，使得对其他所有结点i，w(i)*L(i)的总和最小，其中，L(i)为i到u路径上的所有边的权重和.

SOL: 本题贪心就足够了。记sumW为树上所有节点权重和(仅仅节点)以及WC_i[p]为以p为根的第i颗子树中所有节点权值和(仅仅节点)。如果P是重心，则　"sumW>2*WC_i[p]" 对于所有P的子树i成立--所有子树的权重都小于所有节点权重和的一半。为了找到满足这个条件的节点 用贪心就足够了。随便从一个节点开始，看到哪个子树的权重和超过所有节点权重和一半，就往那个子树移动。直到不能移动位置为止。

[算法]最近看到的几道有意思的题

1 某机器需要处理n个请求，每个请求都有其运行所需的存储空间(R[i])及运行之后输出所占用的存储空间(O[i])，且O[i]小于r[i]。假设CPU只能同时处理一个请求。现在该机器共有m个存储空间，请设计一个算法来安排这n个请求的处理顺序，使得所有请求都能被处理。并简要说明该算法的正确性。如果无论如何安排也不能处理完这些请求，算法也应能给出判断。SOL: 贪心法， 按照R[i]-O[i]降序排列请求

2 在一个空间里有m（m为偶数）只老虎，n只兔子，还有一个你，总共m+n+1只东西（什么，你说你不是东西？）每次随机地抽出两只东西发生互动（通常造成可怕的结果），幸存者再放回去。具体规则如下：
1）老虎和老虎->两相残杀
2）老虎和兔子->老虎吃掉兔子
3）兔子和兔子->没事
4）老虎和你->你成为老虎的美餐
5）你和兔子->你可以选择放回去或煮了兔子
问题是：最后你虎口余生(即，出现山中无老虎，猴子称大王的局面）的概率是多少（你需要在兔子问题上作出最优决策使此概率最大）
SOL: 1/(m+1) 本题最大的trick在于认识到兔子的存在其实根本不影响最后结果，可以直接忽略所有的兔子。剩下m只老虎和一个你。所求概率相当于你排在最后一位的概率。

3 16个人背后各贴一个数字，每个数字都可能取1到16的任意整数值（即可以重复，可以有数字不出现），每个人可以看到其他人的数字，但看不到自己的，贴好数字之后不可以进行任何形式的交流（诸如使用排队次序传达信息之类的伎俩无效），每人猜一个数字，问事先如何安排可以保证至少有一人猜中自己的数字。
SOL: 16个人每个人分别猜自己背后的数字,也就是16个人分别猜16个1-16的数字,显然无法保证一定一人猜中。但是如果16个人集中猜同一个1-16的数字X则能保证一定有一个人猜中, 方法是每一个人分别猜一个数，遍历解空间。这里我们这样人为制造出X:X = X1 xor X2 xor X3... xor X16 (X_i是第i个人背后数字).所以这个X对于所有人是一样的.于是可以第i个人可以猜测一个数Yi,这个数Yi满足和其他所有能看见的人背后的数字的xor之和为i.

[算法]几个有趣的关于数列的O(1)空间O(n)时间小算法

1 数列L中有n个整数。其中有k个数字出现了两次，1个数字出现了一次(所以n=2k+1)。找出只出现一次的那个数字。
解： 将n个数字xor以后，重复出现的就会消失。剩下的就是只出现一次的。

2 数列L中有n个数。已知其中有一个数字出现了至少 n/2+1次。找出这个数字。
解： 用链表存储这n个数字。p指向当前考察的数字。p从链表头开始。如果p和p->next的数字相同，p=p->next，如果不同，则将p和p->next一同从链表中删除。当p->next是链表尾的时候，p就是所求数字。

3 数列L中有n=2k个数字a1,a2,...,an,b1,b2,...,bn。将其变换为a1,b1,a2,b2,...,an,bn。可以将这个问题理解为扑克里的洗牌。
解： 很难的题目。这里有一篇论文http://webhome.cs.uvic.ca/~jellis/perfect.html。