Archive

Posts Tagged ‘字符串’

整理下字符串的一些数据结构和算法

十二月 6th, 2012 2 comments

别看字符串挺简单,还真牵扯到好多数据结构和算法啊,给跪了,要将所有的都好好掌握真心是一项艰难的任务。这里就列举下自己做zoj时候碰到过的一些,然后配合自己做过的例题讲一下。不过每种算法、数据结构具体的描述和代码,还请自己去搜索吧。 阅读更多…

一套可用的后缀数组代码

十二月 6th, 2012 2 comments

后缀数组的代码算法难度比较高,反正没怎么看也不打算看懂,从网上找了好久找到一份比较好用的代码,效率也比较高,据说是用的倍增算法?看不懂 =.= 阅读更多…

一个OOP的AC自动机代码

十二月 6th, 2012 No comments

网上代码很多,但是大多ACMer的风格,呃不是我说,代码可读性和封装性是比较欠缺的…也许Java出身的码农也就这点还有些优势了吧…纯自己手动敲的,build_ac函数(建立fail指针的过程)学习了网上的教程后模仿着写的,而且带clear()释放内存。 阅读更多…

敏感词过滤,PHP实现的Trie树

七月 3rd, 2012 8 comments

项目需求,要做敏感词过滤,对于敏感词本身就是一个CRUD的模块很简单,比较麻烦的就是对各种输入的敏感词检测了。用Trie树来实现是比较通用的一种办法吧,之前一直没机会用过这种数据结构,正好试着写了一下。

因为用PHP实现,关联数组用的很舒服。第一个要解决的是字符集的问题,如果在Java中就比较好办统一的Unicode,在PHP中因为常用UTF-8字符集,默认有1-4个字节不同的长度来表示一个字符,于是写了个Util类来将普通的UTF-8字符串转换成字符数组,每一个元素是一个UTF-8串形成的字符。这一点比较容易实现的,根据UTF-8字符集的格式而来就好。
阅读更多…