
字符串编辑距离的几种实现
春暖花开,踏青时节,我看完了形式语言与自动机这一章这一章提到字符串编辑距离,于是动手实现了几个。编辑距离主要用于拼写纠错,貌似Google 2013的校招笔试题里就有这个。 常见的编辑距离定义 通过插入删除或替换使得一个字符串变为另一个字符...
春暖花开,踏青时节,我看完了形式语言与自动机这一章这一章提到字符串编辑距离,于是动手实现了几个。编辑距离主要用于拼写纠错,貌似Google 2013的校招笔试题里就有这个。 常见的编辑距离定义 通过插入删除或替换使得一个字符串变为另一个字符...
POJ 3259 Wormholes 虫洞:农夫约翰有F个农场,每个农场有N块地,其间有M条路,W条时光隧道(时间倒流)。问是否可能回到过去? 2.5 它们其实都是“图” 最短路 依然很水很基础的 Bellman-Ford 判定负...
POJ 2139 Six Degrees of Cowvin Bacon 六度空间:为了向“六度分割:你和任何一个陌生人之间所间隔的人不会超过五个”致敬,奶牛们决定拍一系列电影叫做……《六度空间》。N头牛,拍了M部电影,同一部电影中的搭档们...
AOJ 0189 Convenient Location 上班族:A桑的实习办公室有多个,公司允许睡办公室,求找出一个办公室使得跑路最短。 2.5 它们其实都是“图” 最短路 基础的任意两点之间的距离Floyd-Warshall算法就行了。...
最小生成树Prim算法 与Dijkstra算法类似,任意挑一个顶点,添加最短边,直至所有顶点都在树中,此时就得到一颗最小生成树了。 证明: 令V为顶点集合,已求得顶点集合为X,V上的最小生成树为T。 假设连接X和V\X的最短边为e,现在需要...
对图的几种初级算法做个总结,温故知新。 最短路问题 Bellman-Ford和Dijkstra的递推公式都是d[i] = min{d[j] + cost[i to j]}。 单源最短路之Bellman-Ford算法 适用于无原点s可达负圈的...
前些时间在BAE上搭了一个应用,数据写入了百度云储存BCS里。现在想将BCS里的数据搬走,但是官方并没有提供一个一键下载的功能。只好自己写了一个,运行良好。 此脚本在本地PHP环境下运行,需要开启CURL拓展。代码里的krumo是一个调试输...
多说还算是WordPress上一款不错的社交网络评论框插件,不过它有“剽窃”博主文章的嫌疑。在wp-content/plugins/duoshuo/WordPress.php中有如下“剽窃”代码: 红色方框内的代码直接将整个post的con...
维特比算法说白了就是动态规划实现最短路径,只要知道“动态规划可以降低复杂度”这一点就能轻松理解维特比算法 维特比算法是一个特殊但应用最广的动态规划算法,利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图——篱笆...
双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树,应用于字符区间大的语言(如中文、日文等)分词领域。 双数组Trie (Double-Array Trie)结构由日本人JUN-ICHI AOE于1989年提出...