Pages
Categories
Archives
-
Recent Posts
Recent Comments
I’m reading
Tags
Blogroll
MyFriends
Meta
-
-
分类目录归档：技术
也谈KMP算法
转眼间，下个学期我们专业就要开《数据结构》这门课程了。想当初我自学数据结构的时候可谓是困难重重，现在我想到有可能我身边的同学们也会遇到和我一样的问题。于是我打算尽我的能力，把我在学习算法的过程中的一点感悟，或者是一些我自认为的难点，用我自己的话描述出来。希望可以给朋友们有所帮助。 我记得我遇到的第一个难题就是KMP算法。 KMP算法是一种改进的字符串匹配算法，由Knuth、Morris、Pratt三位前辈提出来的，取了这三个人的名字的头一个字母。KMP算法采用一种预处理，在不匹配发生的时候这个字符串自身包含足够的信息来确定下一个匹配将在哪里开始，以此避免对以前已匹配的字符的重新检查。 首先，我们简单介绍一下KMP算法的主要思路，然后小戴跟大家详细分析一下KMP中预处理待匹配串的过程。 这里我们举一个例子：假设主字符串Text = “abababababababc”，待查找字符串Pattern=” abababc”。我们用两个指针i和j分别表示Text[i – j + 1…i]与Pattern[1…j]匹配。也就是说，i是不断增长的，随着i的增长j相应的变化以达到Text[i]以前的j个字符与Pattern字符串开头的前j个字符相等。当然，j 越大越好了。现在开始匹配Text[i + 1]和Pattern[j + 1]，如果他们相等，那当然最好了，我们继续i++并且j++。如果不匹配的话，我们的策略是减少j的值使得Text[i – j + 1…i]与Pattern[1…j]相等且Text[i + 1]与Pattern[j + 1]也匹配。当j == Pattern串长度的时候，我们就说Pattern串是Text的子串。 我们来看一下KMP算法具体的处理过程： i = 1 2 3 4 5 6 7 8 9 10 … 继续阅读
腾讯的一道面试题（截取字符串）
题目如下： 假设有“123<em>abc</em>456<em>def</em>789”这么一个字符串，写一个函数，可以传入一个字符串，和一个要截取的长度。返回截取后的结果。 要求： 1、<em>和</em>标记不得计算在长度之内。 2、截取后的字符串，要保留原有<em>标签，不过如果最后有一个标签没有闭合，则去掉其开始标签。 示例： 题中的字符串，要截取长度5，则返回的字符串应该为：123ab；要截取长度8，应返回123<em>abc</em>45。 看到题目后，脑海中首先想到的就是用栈来解决。 代码写得很快，实现起来很简单。但是仔细琢磨一下的话，很容易发现还是有很多问题的。 比如对于一些不需要关闭的标签（如：<br />），这段代码会出现问题。 我先把今天写的代码贴出来，等清闲了再容我仔细推敲一下。 function getSubstr($str, $length) { $result = ”; $tag = ”; $stack = array(); for($i = 0; $i < $length; $i++) { $result .= $str[$i]; if ($str[$i] == ‘<’) … 继续阅读
2010网易编程挑战赛：最大和子序列
原题地址：http://poj.youdao.com/nanti1/C/ 两个dp函数。 #include <cstdio> #include <iostream> using namespace std; #define INF 1000000000 int a[50000], sum[50000]; int n; void init() { scanf("%d",&n); for(int i = 0; i < n; i++) { scanf("%d", &a[i]); sum[i] = (i ? sum[i - 1] + … 继续阅读
棋盘覆盖问题的递归实现
问题描述 在一个2^k x 2^k个方格组成的棋盘中，若恰有一个方格与其他方格不同，则称该方格为一特殊方格，且称该棋盘为一特殊棋盘。显然特殊方格在棋盘上出现的位置有4^k种情形。要用下图所示的4种不同形态的L型骨牌覆盖一个给定的特殊棋盘上除特殊方格外的所有方格，且任何2个L型骨牌不得重叠覆盖。易知，在任何一个2^k x 2^k的棋盘覆盖中，用到的L型骨牌个数恰为(4^k-1)/3。 算法分析 用递归的方法（也称分治法）可以设计解棋盘覆盖问题的一个简捷算法。当k>0时，将2^k x 2^k棋盘分割为4个2^(k-1) x 2^(k-1)子棋盘。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会和处，则这3个子棋盘上被L型骨牌覆盖的方格就成为该棋盘上的特殊方格，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为1×1棋盘。 算法复杂度分析 设T(k)是算法覆盖一个2^k x 2^k棋盘所需的时间，则从算法的分治策略可知，T(k)满足如下递归关系：当k=0时，T(k)=O(1)；当k>0时，T(k)=4T(k-1)+O(1)。解此递归关系得T(k)=O(4^k)。由于覆盖一个2^k x 2^k棋盘所需的L型骨牌个数为(4^k-1)/3，故该算法是一个在渐近意义下最优的算法。 #include <iostream> using namespace std; int tile = 1; // L型骨牌的编号(递增) int board[100][100]; // 棋盘 /***************************************************** * 递归方式实现棋盘覆盖算法 * 输入参数： * currentRow：当前棋盘左上角的行号 … 继续阅读
2010网易编程挑战赛：有“道”难题
原题地址：http://poj.youdao.com/nanti2/A/ Description ‘道’是中国古代哲学的重要范畴。用以说明世界的本原、本体、规律或原理。在不同的哲学体系中，其涵义有所不同。老子所写的《道德经》是关于‘道’的经典著作。 道的原始涵义指道路、坦途，以后逐渐发展为道理，用以表达事物的规律性。这一变化经历了相当长的历史过程。《易经》中有“复自道，何其咎”（《小畜》），“履道坦坦”（《履》），“反复其道，七日来复”(《复》)，都为道路之义。 《尚书•洪范》中说：“无有作好,遵王之道；无有作恶,遵王之路。无偏无党,王道荡荡;无党无偏,王道平平；无反无侧,王道正直”。这里的道，已经有正确的政令、规范和法度的意思,说明“道”的概念已向抽象化发展。 —- 节选自有道词典(http://dict.youdao.com) Base64是网络上最常见的用于传输8Bit字节代码的编码方式之一。它把每三个8Bit的字节转换为四个6Bit的字节（3*8 = 4*6 = 24），然后把6Bit再添两位高位0，组成四个8Bit的字节，也就是说，转换后的字符串理论上将要比原来的长1/3。 有道的工程师闲暇之余，将Base64编码改成了Base4编码，即把每个8Bit的字节转换成4个2Bit的字节，然后以4个字符来代替。编码和字符的对应方案如下： 00 —- a 01 —- o 10 —- d 11 —- 空格 这样，编码后的字符串就只会含有字符‘d’,’a’,’o’和空格。 例如字符y ,其ASCII码是121，对应的二进制串是01111001，这样分成 01 11 10 01四块后，用Base4编码后的字符串为”o do”。 有道的工程师很好奇，按照这种编码方式，编码后的字符串中含有多少个完整的dao呢？一个完整的dao由连续的‘d’,’a’,’o’三个字符组成。 Input 第一行有一个正整数n，代表接下来有n个待编码的原串。（1 <= n <= 10) … 继续阅读
2010网易编程挑战赛：有道搜索框
原题地址：http://poj.youdao.com/nanti1/B/ Description 在有道搜索框中，当输入一个或者多个字符时，搜索框会出现一定数量的提示，如下图所示： 现在给你N个单词和一些查询，请输出提示结果，为了简化这个问题，只需要输出以查询词为前缀的并且按字典序排列的最前面的8个单词，如果符合要求的单词一个也没有请只输出当前查询词。 Input 第一行是一个正整数N，表示词表中有N个单词。 接下来有N行，每行都有一个单词，注意词表中的单词可能有重复，请忽略掉重复单词。所有的单词都由小写字母组成。 接下来的一行有一个正整数Q，表示接下来有Q个查询。 接下来Q行，每行有一个单词，表示一个查询词，所有的查询词也都是由小写字母组成，并且所有的单词以及查询的长度都不超过20，且都不为空 其中：N<=10000,Q<=10000 Output 对于每个查询，输出一行，按顺序输出该查询词的提示结果，用空格隔开。 Sample Input 10 a ab hello that those dict youdao world your dictionary 6 bob d dict dicti yo z Sample Output bob dict dictionary dict dictionary dictionary … 继续阅读
2010网易编程挑战赛：另类的异或
原题地址：http://poj.youdao.com/nanti1/A/ Description 对于普通的异或，其实是二进制的无进位的加法 这里我们定义一种另类的异或A op B, op是一个仅由^组成的字符串，如果op中包含n个^，那么A op B表示A和B之间进行n+1进制的无进位的加法。 下图展示了3 ^ 5 和 4 ^^ 5的计算过程 Input 第一行有一个正整数T, 表示下面共有T组测试数据。 接下来T行，每行有一组测试数据，是由空格隔开的三个部分组成： A B C A和C是两个十进制整数，B是一个字符串，由n个^组成 1 <= T <= 100, 0<=A,B<2^30, 1<=n<=1000 Output 每个测试数据输出一行，包含一个数字，即该数据的结果，用十进制表示。 Sample Input 2 3 ^ 5 4 … 继续阅读
解决Visual C++ 编译器中混合 .c 文件时收到 C1853 预编译头错误的方法
当 Visual C++ 项目启用了预编译头 (Precompiled header) 功能时，如果项目中同时混合有 .c 和 .cpp 源文件，则可能收到 C1853 编译器错误：fatal error C1853: ‘pjtname.pch’ precompiled header file is from a previous version of the compiler, or the precompiled header is C++ and you are using it from C … 继续阅读
phpMyAdmin中的UTF8中文乱码
基本上做过Web开发的朋友都有过和乱码做斗争的经历吧，而写PHP搭配MySQL的绝大多数朋友会选择phpMyAdmin这个工具。那么今天我们来谈谈在phpMyAdmin中可能遇到的一种UTF-8中文乱码的问题。 问题描述：网站采用UTF-8编码，前台浏览正常，在phpMyAdmin里查看中文变成乱码。 一般来说，我们安装的Web服务器软件，例如Apache，默认的编码都不是UTF-8。当我们从以UTF-8编码的页面中的表单输入数据的时候，因为在我们输入的时候这些数据本身是用UTF-8编码的，而当表单提交的时候这些用UTF-8编码的数据会经过数据库的处理后再存入表中，所以它会把这些UTF-8编码的数据以其默认编码存入到数据库中，于是变成了乱码。这些乱码仍然是用UTF-8编码的，只是被数据库的默认编码给弄乱了。这也就可以解释为什么我们在网站的前台读取数据的时候却能够看到正常的中文字符串。 在这种情况下，不管我们在phpMyAdmin中将字段的整理改成utf8_general_ci、utf8_unicode_ci或latin1_swedish_ci等编码都是没用的，看到的只能是乱码而不能读出正常的中文字符串。 如果你想要在phpMyAdmin中也看到正常的中文，下面我提供两种解决方案： 1、更改MySQL的默认编码 1.1、Linux环境下 找到 /etc/my.cnf 只需要对该文件的两个地方做如下修改就可以将MySQL的默认编码改成UTF-8 [mysqld] default-character-set=utf8 [client] default-character-set=utf8 1.2、Windows环境下 如果你使用的是Windows，那么在MySQL的配置文件my.ini里做上述同样的就该即可。 2、通过程序限定MySQL的数据传输编码 在连接数据库时加入如下代码，就可以告知MySQL采用UTF-8编码传输数据了： mysqli_query($dbc, “SET NAMES ‘UTF8′”); 如下图所示 通过如上任意一种修改，你就可以解决在phpMyAdmin里中文显示为乱码的问题啦。