计算最长前缀回文子串，可以利用字符串匹配算法KMP的Next数组，然后原串和reverse串拼接之后，算Next，要多算一个，可以采用加一个字符的办法，最后一个Next值就是需要的信息。

写一个函数，可以从给定的概率分布中采样，暂时考虑连续概率分布。

但是，如果从编程角度来实现，似乎不好实现。

这里介绍一个ITM(Inversion Transform Method)算法，
引用自码代码的张洋，该大神用JS轮着实现了一遍这些算法。
http://blog.codinglabs.org/articles/methods-for-generating-random-number-distributions.html

该算法依赖于一个条件就是，概率分布函数需要有反函数

ITM算法描述

1. 生成一个服从均匀分布的随机数U∼Uni(0,1)
2. 设F(X)为指定分布的CDF，F−1(Y)是其逆函数。返回X=F−1(U)作为结果

我们从横轴上标注两点xa和xb，其CDF值分别为F(xa)和F(xb)。

由于U服从0到1之间的均匀分布，因此对于一次U的取样，U落入F(xa)和F(xb)之间的概率为:

P(U∈(F(xa),F(xb)))=F(xb)−F(xa)
而由于CDF都是单调非减函数，因此这个概率同时等于X落入xa和xb之间的概率，即：

P(U∈(F(xa),F(xb)))=P(F−1(U)∈(F−1(F(xa)),F−1(F(xb))))=P(X∈(xa,xb))=F(xb)−F(xa)
而根据CDF的定义，这刚好说明X服从以F(x)为CDF的分布，因此我们的生成算法是正确的。

关键是一个利用反函数来实现的，因为CDF全都是[0,1]之间的值域，
我们需要按照给定分布去采样。

一般来说ITM是一种很好的算法，简单且高效，如果可以使用的话，是第一选择。但是ITM有自身的局限性，就是要求必须能给出CDF逆函数的解析表达式，有些时候要做到这点比较困难，这限制了ITM的适用范围。

当无法给出CDF逆函数的解析表达式时，Acceptance-Rejection Method（下文简称ARM）是另外的选择。ARM的适用范围比ITM要大，只要给出概率密度函数（下文简称PDF）的解析表达式即可，而大多数常用分布的PDF是可以查到的。

ARM算法描述

设PDF为f(x)。首先生成一个均匀分布随机数X∼Uni(xmin,xmax)
独立的生成另一个均匀分布随机数Y∼Uni(ymin,ymax)
如果Y≤f(X)，则返回X，否则回到第1步

Posted by richard爱闹 - 5月 21 2015
如需转载，请注明： 本文来自 Richard