[翻译]Ruby教程2——词法结构

Ruby 词法结构

计算机语言跟人类语言类似也有词法结构。一个Ruby程序的源代码由符号构成。符号标志是最基本的代码元素。在Ruby语言中我们有多种词法结构,如:注释、变量、字面量、空白符号、操作符、分隔符和关键字。


注释


注释是用于向人们阐明源代码。在Ruby中有两种注释的方法,单行注释和多行注释。单行注释以#字符开始;多行注释是放置在=bgin=end 等号标志之间。



#!/usr/bin/ruby


=begin



comments.rb

author Jan Bodnar

ZetCode 2011



=end


# prints message to the terminal

puts “Comments example”



这个例子同时展示的两种方法的注释。注释的内容将会被Ruby解释器忽略掉。



=begin
comments.rb
author Jan Bodnar
ZetCode 2011
=end


这是一个多行注释的例子,两个符号标志必须在行首。


空白符号


在源文件中Ruby的空白符号被用于分隔符号标志和结束语句。它也用于增强代码的可读性。


if true then

  puts “A message”

end


空白字符在一些时候是必须的。例如在if关键字和true关键字之间;或者在puts方法和实际的字符串之间。而有时它又是被禁止的,如它不能包含在变量标识符或者语言关键字中。


a=1

b = 2

c  =  3


这些在符号标志之间的空白字符对于Ruby解释器是无关紧要的。但是它于整个项目的风格统一非常重要。





#!/usr/bin/ruby


x = 5 + 3

puts x


x = 5

    + 3

puts x


x = 5 +

    3

puts x



换行是一种用于结束语句的空白字符形式。


x = 5 + 3


在第一种情况,我们有一条语句。它将相加求和的值赋给x变量。这个变量的值为8。


x = 5

     +3


现在第二种情况。第1条语句被换行符终止了,x变量的值是5。另一条语句+3,没有任何影响。


x = 5 +

     3


最后,第1条语句的换行符之前有一个+二元操作符,因此解释器期望另一个值,它将检查第二行。在这种情况它将这两种作为一条语句,因此x这是的值为8。


$ ./whitespace.rb

8

5

8


以上为输出结果。


变量


变量是一个保存了值的标识符。在编程时我们说我们给一个变量分配一个值。专业一点的说法是一个变量是对计算机中存储了值的内存的引用。在Ruby中一个变量可以保存字符串、数字或者多种对象。不同时间变量可以被分配不同的值。

在Ruby中变量名由字母数字和下划线组成,但是不能以数字开头。Ruby解释器可以很容易地区分原始的数字跟变量。变量名不能以大写字母开头,在Ruby中以大写字母开头的标识符会被认为是一个常量。



Value

value2

company_name



以上这些都是合法的变量名。



12Val

exx$

first-name



以上这些都不是合法的变量名。


变量名前可以加$@这两个特殊的字符,它们用于创建特殊作用域的变量。


变量名是大小写敏感的,这意味着pricepRice是两个不同的标识符。



#!/usr/bin/ruby

number = 10

numBER = 11


puts number, numBER



在这个脚本中我们给两个标识符分配了两个数字。numbernumBER是两个不同的变量。



$ ./case.rb

10

11



以上是这个脚本运行的输出结果。


常量


常量的值在程序运行过程中是不变的。在Ruby中一个标识符的首字母大写即为一个常量。编程时对于常量约定是所有字母全都大写。

与其他语言不同,Ruby不会强制要求常量的值始终不变。当我们给一个常量分配新的值时解释器只会提示一个警告。



#!/usr/bin/ruby

Name = “Robert”

AGE = 23

Name = “Juliet”



在上面的例子中我们创建了两个常量,其中一个被重新定义了。



Name = “Robert”

AGE = 23



创建两个常量。在Ruby中标识符的首字母大写即定义为常量。作为约定常量通常是所有字母都大写的。



Name = “Juliet”



我们重新定义了一个常量,这会引起一个警告。



$ ./constants.rb

./constants.rb:6: warning: already initialized constant Name



以上是这个例子运行的输出。


字面量


字面量(literal)是按原文本内容所表示的特殊类型的值。字面量类型包括布尔型、整型、浮点型、字符串、字符和日期。专业的说一个字面量在编译时会分配一个值,该值在运行时会分配给对应的变量。



age = 29

nationality = “Hungarian”



这里我们分配了两个字面量变量。数字29和字符串“Hungarian”都是字面量。


#!/usr/bin/ruby

require ‘date’

sng = true
name = “James”
job = nil
weight = 68.5
born = Date.parse(“November 12, 1986”)

puts “His name is #{name}”

if sng == true
puts “He is single”
else
puts “He is in a relationship”
end

puts “His job is #{job}”
puts “He weighs #{weight} kilograms”
puts “He was born in #{born}”

在上面这个例子中,我们使用了多个字面量。布尔字面量的值可能为true或者falseJames是一个字符串字面量,nil表示一个不存在的值,68.5是一个浮点数,最后November 12,1986是一个日期。



$ ./literals.rb

His name is James

He is single

His job is

He weighs 68.5 kilograms

He was born in 1986-11-12



以上为literals.rb脚本的输出结果。


代码块


Ruby语句通常是放在代码块中。一个代码块可以被{}符号或者doend关键字分隔。


#!/usr/bin/ruby

puts [2, -1, -4, 0].delete_if { |x| x < 0 }

[1, 2, 3].each do |e|
puts e
end

这个例子中我们展示了两个代码块。


Ruby代码的控制流通常是使用if关键字。这个关键字k跟随着一个代码块,在这种情况下代码块被thenend关键字分隔,then关键字是可选的。


#!/usr/bin/ruby

if true then
puts “Ruby language”
puts “Ruby script”
end

在上面这个例子中,我们展示了一个简单的代码块。它有两条语句。这个代码块被thenend关键字分隔。then关键字可以省略。


符号


符号$@是特殊字符用于表示变量的作用域,$表示全局变量,@表示实例变量,@@表示类变量。



$car_name = “Peugeot”

@sea_name = “Black sea”

@@species = “Cat”



这些符号总是位于变量标识符的开头。


操作符


操作符是一个用于对值执行一个动作的符号。


!    +    -    ~        **    /    %
<< >> & | ^
== === != <=> >= >
< <= = %= /= -=
+=
= *= .. … not
and or ?: && ||

以上是在Ruby中所有有效的操作符,我们将在之后的教程中介绍它们。


分隔符


分隔符是一个或多个用于在纯文本或者其他数据流中指定分隔独立区域范围的字符序列。


(       )       [       ]       {       }
, ; ‘ “ | |

#!/usr/bin/ruby

name = “Jane”
occupation = ‘Student’
numbers = [ 2, 3, 5, 3, 6, 2 ]

puts name; puts occupation
puts numbers[2]
numbers.each { |i| puts i }
puts ( 2 + 3 )
5

在上面这个例子中我们展示多种Ruby分隔符的用法。



name = “Jane”

occupation = ‘Student’



在Ruby中单引号和双引号被用于分隔字符串。



numbers = [ 2, 3, 5, 3, 6, 2 ]



中括号用于指定数组的范围。逗号用于分隔数组项。



puts name; puts occupation



在Ruby中分号用于分隔两条语句。



puts numbers[2]



分隔符可用于不同的环境中,这里中括号用于访问数组。



numbers.each { |i| puts i }



大括号用于定义代码块。管道用于定义在每次循环中被当前数组项所填充的元素。



puts ( 2 + 3 ) * 5



括号用于改变一个表达式的求值。


关键字


关键字是在Ruby语言中被保留的字。关键字用于在计算机程序中展示特定的任务。例如:在终端中打印一个值,执行重复的任务或者展示逻辑操作。程序员不能使用关键字作为普通的变量。


alias    and      BEGIN      begin    break    case
class def defined? do else elsif
END end ensure false for if
in module next nil not or
redo rescue retry return self super
then true undef unless until when
while yield

这些是Ruby的关键列表。


以上就是Ruby的词法结构了。




原文地址: http://zetcode.com/lang/rubytutorial/lexis/

翻译:龙昌 admin@longchangjin.cn

完整教程:https://github.com/wusuopu/Ruby-tutorial

[翻译]Ruby教程1——Ruby语言介绍

Ruby

在这部分Ruby教程中,我们将介绍Ruby编程语言。


目标


这个教程的目标是让你入门Ruby。这个教程覆盖了Ruby的主要内容,包括变量、表达式、集合、流程控制结构以及其他的一些主要特性。同样也会描述一些高级的概念,例如面向对象和正则表达式。这不会完全地覆盖这个语言。


Ruby


Ruby是一门动态的、反射的、通用的面向对象编程语言。它的源作者是一个日本程序员——松本行弘 (まつもとゆきひろ)。Ruby第一次发表是在1995年。


Ruby支持多种程序范式。包括面向对象、反射、命令式的和反射的编程。Ruby语言主要是受到Perl、Smalltalk、Eiffel和Lisp的影响。不同于java、C#以及C,Ruby没有官方的规范。取而代之的是用原始的C实现的Ruby语言作为实际参考。同时也还存在一些用其他方法实现的Ruby语言,如:JRuby、IronRuby或者MacRuby。


Ruby的官方网站是: ruby-lang.org


人气


如今有上百种编程语言,而Ruby属于最流行的一个。在langpop.comtiobe网站Ruby都排在第10名左右。Ruby on Rails——一个非常流行的web应用框架是使用Ruby开发第一个杀手级的应用。


交互式的解释器


我们可以通过脚本或者交互式的解释器来运行Ruby语句。在这个教程中我们将使用交互式的Ruby会话来展示一些小的代码片段。大的代码例子将放在Ruby脚本中。



$ irb

irb(main):001:0> puts RUBY_VERSION

2.0.0

=> nil



这是一个Ruby交互会式会话的例子。我们在终端中打印了一个特别的常量RUBYVERSION,它被设置为当前使用的Ruby的版本。

译注:原文的作者使用的是ruby 1.8.7,而如今ruby最新版已经是2.0.0了,因此我在翻译的时候也结合了当前新的内容。


Ruby脚本


我们开始我们的第一个简单的Ruby脚本例子。



#!/usr/bin/ruby

# first.rb

puts “This is Ruby”



这个脚本我们将在终端上打印一条消息。



#!/usr/bin/ruby



UNIX下的每一个脚本都是以shebang符号开始的。shebang是脚本中开始的前两个字符:#!。shebang后面是执行我们脚本的解释器的路径。/usr/bin是Ruby解释器最常用的位置。它也可以定位在/usr/local/bin或者其他什么地方。



# first.rb



在Ruby中注释是以#开始。



puts “This is Ruby”



puts方法是将字符串打印到终端。



$ which ruby

/usr/bin/ruby



Ruby解释器的路径可以使用which命令找到。



$ chmod +x first.rb

$ ./first.rb

This is Ruby



通过chmod命令,我们给脚本增加可执行的权限。


资源


以下资源在编写该教程时会使用到:

ruby-lang.org

ruby-doc.org

<a href=”http://en.wikipedia.org/wiki/Ruby(programming_language)”>Ruby article on wikipedia.org

ruby.runpaint.org


在这章的教程中我们介绍了Ruby语言。




原文地址: http://zetcode.com/lang/rubytutorial/ruby/

翻译:龙昌 admin@longchangjin.cn

完整教程:https://github.com/wusuopu/Ruby-tutorial

Scrapy框架学习笔记3—— Scrapy与mongodb结合

创建一个新的Item Pipeline,并将其添加到settings.py的ITEM_PIPELINES列表中。
在process_item方法中将item的数据保存到mongodb中。
scrapy的Item与dict相似,而mongodb中的数据是心bson格式保存的。因此Item的数据应该可以直接存储到mongodb中而几乎不用做额外的处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class MyMongoDBPipeline(object):
def __init__(self, mongodb_server, mongodb_port, mongodb_db, mongodb_collection):
connection = pymongo.Connection(mongodb_server, mongodb_port)
self.mongodb_db = mongodb_db
self.db = connection[mongodb_db]
self.mongodb_collection = mongodb_collection
self.collection = self.db[mongodb_collection]

@classmethod
def from_crawler(cls, crawler):
# 连接mongodb
return cls('localhost', 27017, 'scrapy', 'items')

def process_item(self, item, spider):
result = self.collection.insert(dict(item))
log.msg("Item %s wrote to MongoDB database %s/%s" % (result, self.mongodb_db, self.mongodb_collection),
level=log.DEBUG, spider=spider)
return item

Scrapy框架学习笔记2—— Scrapy与Django结合

前面也介绍过了Scrapy与Django的设计思想非常相似,因此这个两个结合也是比较容易的。
以下方法在Scrapy 0.18与Django 1.5下面测试是可以用的。

1.首先设置Django的运行环境


在settings.py中添加如下代码:

1
2
3
4
5
6
7
8
def setup_django_environment(path):
import imp, os, sys
from django.core.management import setup_environ
m = imp.load_module('settings', *imp.find_module('settings', [path]))
setup_environ(m)
sys.path.append(os.path.abspath(os.path.join(path, os.path.pardir)))

setup_django_environment("/django/project/path")

注意:如果你的Django项目是用的sqlite数据库的话,那就需要设置为绝对路径,不能使用相对路径。

2.创建django item


首先在Django项目代码中创建一个Django的model,例如:

1
2
3
4
5
from django.db import models
class ScrapyModel(models.Model):
title = models.CharField(max_length=200)
link = models.CharField(max_length=200)
desc = models.TextField()

然后在Scrapy项目中创建一个新的Item,只不过这次我们不再是继承自scrapy.item.Item,而是scrapy.contrib.djangoitem.DjangoItem:

1
2
class Test1DjItem(DjangoItem):
django_model = ScrapyModel

用法与原来的Item相同,只是最后要执行一个save函数来调用django的save方法将数据存入数据库。

Scrapy框架学习笔记1——概括

Scrapy是一个python的web爬虫框架,其设计思想与Django非常相似。如果事先用过Django的话那么理解Scrapy应该不难。

0.安装Scrapy


当前Scrapy的稳定版本是0.18
使用pip进行安装: pip install Scrapy
使用easy_install进行安装: easy_install Scrapy


初次使用可以按照它的官方教程操作,先熟悉一下:
http://doc.scrapy.org/en/0.18/intro/tutorial.html


1.一个项目的基本流程


创建新项目 scrapy startproject <name>

然后在<name>/spiders目录下新建一个python文件。
编写一个新的class继承自 scrapy.spider.BaseSpider,并且需要设置如下属性:
name: 该爬虫的名字,不能与其它的相同 start_urls: 开始的url入口
parse(): 对从start_urls的获取的内容进行处理的函数,需要一个Response参数 allowed_domains: 一个列表,表示该爬虫允许爬取的网站域名。可选

爬虫运行流程:
首先调用 start_requests()方法访问start_urls的链接(默认的),然后由parse回调方法对请求的响应进行处理。 在回调中处理Response,并返回Item或者Request,再或者是由这两种对象组成的一个可迭代的对象。
Request对象对应的callback可以与parse相同,也可以不同。


最后运行这个爬虫脚本: scrapy crawl name

也可以直接在终端运行一个选择器: scrapy shell <url>


2.使用Item

scrapy.item.Item的调用接口类似于python的dict,Item包含多个scrapy.item.Field。  
这跟django的Model与Field有点相似。  
Item通常是在Spider的parse方法里使用,它用来保存解析到的数据。

3.使用Item Pipeline

在settings.py中设置ITEM_PIPELINES,其默认为[],与django的MIDDLEWARE_CLASSES等相似。
从Spider的parse返回的Item数据将依次被ITEM_PIPELINES列表中的Pipeline类处理。

一个Item Pipeline类必须实现以下方法:

process_item(item, spider)

为每个item pipeline组件调用,并且需要返回一个scrapy.item.Item实例对象或者抛出一个scrapy.exceptions.DropItem异常。
当抛出异常后该item将不会被之后的pipeline处理。
参数:
item (Item object) – 由parse方法返回的Item对象
spider (BaseSpider object) – 抓取到这个Item对象对应的爬虫对象

也可额外的实现以下两个方法:
open_spider(spider)

当爬虫打开之后被调用。
参数: spider (BaseSpider object) – 已经运行的爬虫

close_spider(spider)

当爬虫关闭之后被调用。
参数: spider (BaseSpider object) – 已经关闭的爬虫

4.保存数据

想要保存抓取到的数据,最简单的方法是使用Feed exports。 参考官方文档:http://doc.scrapy.org/en/0.18/topics/feed-exports.html#topics-feed-exports

例如将抓取的数据导出为json: scrapy crawl dmoz -o items.json -t json

对于小项目用这种方法也足够了。如果是比较复杂的数据的话可能就需要编写一个Item Pipeline进行处理了。

分享几款vim风格的浏览器

作为一个了vim用户,希望所有的操作都能够以vim的按键方式完成,上网浏览网页也不例外。于是乎就找了几款vim按键绑定的浏览器。

0.Firefox + Vimperator / Chrome + Vimium
如果是用的Firefox或者Chrome浏览器的话直接安装相应的插件即可达到想要的效果。
Firefox的是Vimperator;Chrome的是Vimium。

但是感觉Firefox和Chrome有时又太占资源了,我想到一个轻量级的浏览器。

1.w3m
如果你是一个终端控的话,w3m貌似还不错。现在常见的Linux发行版的软件源中应该都包含了w3m,直接通过软件仓库安装就行了。
只不过w3m太简洁了,显示不了CSS样式,执行不了js代码,甚至是显示图片都比较麻烦。

2.uzbl
uzbl是一款基于GTK+Webkit的浏览器,只是它的按键与原生的vim相差比较大,我刚开始操作不太适应。
它的配置文件在$HOME/.config/uzbl目录下,如果把它配置好了的话那使用起来应该也会很不错的。
uzbl默认是不支持多标签的,如果要想打开多个标签请运行uzbl-tabbed程序。
下载地址:http://www.uzbl.org/

linuxdeepin用户可以执行命令 sudo apt-get install uzbl来安装。

3.dwb
dwb是一款基于gtk和webkit的轻量级的浏览器。它的按键与Firefox的Vimperator插件较为相似。
我个人觉得dwb是这几款浏览器中最为方便的,它配置比较简单,而且提供了一个web的配置页面。如图:

下载地址:http://portix.bitbucket.org/dwb/

4.luakit
luakit也是基于gtk和webkit的,只不过它是用lua语言开发的。它的配置文件也是lua脚本,如果想到修改配置的话可能需要懂点lua语言。
我感觉luakit的按键与vim最相近,而且它还提供了页面调试功能,这对做web开发的人来说比较方便。

下载地址:http://mason-larobina.github.io/luakit/

linuxdeepin用户可以执行命令 sudo apt-get install luakit来安装。

分享两个vim的git插件

1.vim-git

我只是简单体验发一下,个人觉得这个就是用vim的命令把git的命令包装了一下,还不如直接在终端下操作方便。

常用命令
:GitAdd
:GitCommit
:GitStatus
:GitLog
:GitCheckout
:GitDiff
:GitPull
:GitPush

快捷键
<Leader>gd 等同于 :GitDiff
<Leader>gD 等同于 :GitDiff —cached
<Leader>gs 等同于 :GitStatus
<Leader>gl 等同于 :GitLog
<Leader>ga 等同于 :GitAdd
<Leader>gA 等同于 :GitAdd <cfile>
<Leader>gc 等同于 :GitCommit

下载地址:https://github.com/motemen/git-vim.git

2.vim-fugitive

感觉这个比较强大,尤其是配合vimdiff来查看文件的发动非常方便。
它的说明文档介绍到如果你的vim版本低于7.2,那么建议同时也把vim-git安装上。

下载地址:https://github.com/tpope/vim-fugitive.git

md5的一个碰撞例子

md5作为计算机安全领域广泛使用的一种散列函数,被用于检测信息是否完整一致。

然而在2004年8月17日的美国加州圣巴巴拉,正在召开的国际密码学会议(Crypto’2004)上来自山东大学的王小云教授做了破译MD5、HAVAL-128、 MD4和RIPEMD算法的报告。她公布了MD系列算法的破解结果。

各位好奇的可以在网上搜索王小云老师的那篇论文,反正我是看不懂的。不过倒是找到了一个md5碰撞的例子,于是就拿来分享一下。

比如有两个文件test1、test2,文件的十六进制内容分别如下:

% xxd test1            
0000000: 0e30 6561 559a a787 d00b c6f7 0bbd fe34  .0eaU..........4
0000010: 04cf 0365 9e70 4f85 34c0 0ffb 659c 4c87  ...e.pO.4...e.L.
0000020: 40cc 942f eb2d a115 a3f4 155c bb86 0749  @../.-.....\...I
0000030: 7386 656d 7d1f 34a4 2059 d78f 5a8d d1ef  s.em}.4. Y..Z...

% xxd test2
0000000: 0e30 6561 559a a787 d00b c6f7 0bbd fe34  .0eaU..........4
0000010: 04cf 0365 9e74 4f85 34c0 0ffb 659c 4c87  ...e.tO.4...e.L.
0000020: 40cc 942f eb2d a115 a3f4 15dc bb86 0749  @../.-.........I
0000030: 7386 656d 7d1f 34a4 2059 d78f 5a8d d1ef  s.em}.4. Y..Z...

如果想得到文件的原始内容,可以把上面的输出信息保存为一个文本文件(如test.txt),然后再执行命令 xxd -r test1.txt > test 即可。
从上面可以看到这两个文件的内容明显是不一样的,那么现在就来计算一下这两个文件的md5值吧。

% md5sum test1
cee9a457e790cf20d4bdaa6d69f01e41  test1
% md5sum test2
cee9a457e790cf20d4bdaa6d69f01e41  test2

从计算结果可以看到,虽然这两个文件内容不同,但是它们的md5值却是相同的。这个就是所谓的碰撞。

Python中的字符串匹配算法分析

在Python在str对象的find、index、replace等操作都是基于字符串匹配的。通过阅读Python的源代码可知,在Python中的字符串匹配算法是基于Boyer-Moore、Horspool和Sunday的混合。

关于它的详细介绍可以访问这个网页: http://effbot.org/zone/stringlib.htm

用Python代码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/env python
#-*- coding:utf-8 -*-


def make_delta1(p):
ALPHABET_LEN = 256
i = 0
patternlen = len(p)
delta1 = [0] * ALPHABET_LEN

while i < ALPHABET_LEN:
delta1[i] = patternlen
i += 1

i = 0
while i < patternlen-1:
delta1[ord(p[i])] = patternlen-1 - i
i += 1
return delta1


def find(s, p):
# find first occurrence of p in s
n = len(s)
m = len(p)
delta1 = make_delta1(p)
skip = delta1[ord(p[m-1])]
i = 0
while i <= n-m:
if s[i+m-1] == p[m-1]: # (boyer-moore)
# potential match
if s[i:i+m-1] == p[:m-1]:
return i
if s[i+m] not in p:
i = i + m + 1 # (sunday)
else:
i = i + skip # (horspool)
else:
# skip
if s[i+m] not in p:
i = i + m + 1 # (sunday)
else:
i = i + 1
return -1 # not found

if __name__ == '__main__':
print find("HERE IS A SILMPLE EXAMPLE", "EXAMPLE")

字符串匹配算法(五)——Horspool算法

Horspool算法是Boyer-Moore算法的一个简化版,全名叫做Boyer-Moore-Horspool算法。

Horspool算法的基本思想是将文本串text中匹配窗口的最后一个字符跟模式串pattern中的最后一个字符比较。如果相等,继续从后向前对主串和模式串进行比较,直到完全相等或者在某个字符处不匹配为止 。如果不匹配,则根据文本串匹配窗口中的最后一个字符β在模式串中的下一个出现位置将窗口向右移动;若字符β没有在模式串中出现,则直接将整个模式串滑过这一位。

同样的举个例子来说明一下。假定文本串text为:”HERE IS A SIMPLE EXAMPLE”,长度为n;模式串pattern为:”EXAMPLE”,长度为m;现在要在text中搜索看看是否包含pattern。

1).


HERE IS A SIMPLE EXAMPLE
EXAMPLE

‘S’与’E’匹配失败,并且’S’没有在pattern中出现,所以直接将pattern滑过’S’这一位。

2).


HERE IS A SIMPLE EXAMPLE
EXAMPLE

这时’P’与’E’匹配失败,但是’P’在模式串pattern中出现了,所以把pattern向右移,使得text中的’P’与pattern中的’P’对齐。

3).


HERE IS A SIMPLE EXAMPLE
EXAMPLE

然后重复执行之前的操作。

用C语言实现如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <string.h>
#include <limits.h>

/* Returns a pointer to the first occurrence of "needle"
* within "haystack", or NULL if not found. Works like
* memmem().
*/

/* Note: In this example needle is a C string. The ending
* 0x00 will be cut off, so you could call this example with
* boyermoore_horspool_memmem(haystack, hlen, "abc", sizeof("abc"))
*/
const unsigned char *
boyermoore_horspool_memmem(const unsigned char* haystack, size_t hlen,
const unsigned char* needle, size_t nlen)
{
int index = 0;
size_t scan = 0;
size_t bad_char_skip[UCHAR_MAX + 1]; /* Officially called:
* bad character shift */

/* Sanity checks on the parameters */
if (nlen <= 0 || !haystack || !needle)
return NULL;

/* ---- Preprocess ---- */
/* Initialize the table to default value */
/* When a character is encountered that does not occur
* in the needle, we can safely skip ahead for the whole
* length of the needle.
*/
for (scan = 0; scan <= UCHAR_MAX; scan = scan + 1)
bad_char_skip[scan] = nlen;

/* C arrays have the first byte at [0], therefore:
* [nlen - 1] is the last byte of the array. */
size_t last = nlen - 1;

/* Then populate it with the analysis of the needle */
for (scan = 0; scan < last; scan = scan + 1)
bad_char_skip[needle[scan]] = last - scan;

/* ---- Do the matching ---- */

/* Search the haystack, while the needle can still be within it. */
while (hlen >= nlen)
{
/* scan from the end of the needle */
for (scan = last; haystack[scan] == needle[scan]; scan = scan - 1)
if (scan == 0) /* If the first byte matches, we've found it. */
{
printf("index: %d\n", index-1);
return haystack;
}

/* otherwise, we need to skip some bytes and start again.
Note that here we are getting the skip value based on the last byte
of needle, no matter where we didn't match. So if needle is: "abcd"
then we are skipping based on 'd' and that value will be 4, and
for "abcdd" we again skip on 'd' but the value will be only 1.
The alternative of pretending that the mismatched character was
the last character is slower in the normal case (E.g. finding
"abcd" in "...azcd..." gives 4 by using 'd' but only
4-2==2 using 'z'. */
hlen -= bad_char_skip[haystack[last]];
index += bad_char_skip[haystack[last]];
haystack += bad_char_skip[haystack[last]];
}

return NULL;
}


int main(int argc, char *argv[])
{
char text[] = "HERE IS A SILMPLE EXAMPLE";
char pattern[] = "EXAMPLE";
char *result = boyermoore_horspool_memmem(text, strlen(text), pattern, strlen(pattern));
if (result)
{
printf("result: %s\n", result);
} else {
printf("failed!\n");
}
return 0;
}