有道难题

    有道的工程师闲暇之余，将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'三个字符组成。
输入
    第一行有一个正整数n，代表接下来有n个待编码的原串。（1 <= n <= 10)
    接下来有n行，每行有一个长度不超过106的原串，原串中的字符可能为ASCII码中除换行符以外的任意可见字符。
输出
    共有n行，每行为一个整数k, 表示输入数据中对应的原串用Base4编码后含有多少个完整的dao。
样例输入

    2
    www.youdao.com
    dict.youdao.com

样例输出

    1
    1





以上是“有道难题” 的一个题目，限定用Java或者C系列的语言写，那些东西我都差不多忘光了，实在写不出来。稍微熟悉一点的就是Ruby了，写了个大概的（不完整），希望大家多提意见，也把自己的代码拿出来亮亮。

s="www.youdao.com/youdao"

t=s.unpack("B*")
g=[]
t=t.split(//)
t.each_with_index do |x,i|
	if i%2!=0
	 g<<[t[i-1],x]
	end
end

g.map!{|x|x.to_s}
p g
g.map! do |x|
	case x
	when "00"
	  "a"	  
	when "01"
	   "o"
	when "10"
	   "d"
	when "11"
	   " "	   
	end
end

	p g.to_s.scan(/dao/).size

 

 

 table = {'00'=>'a','01'=>'o','10'=>'d','11'=>' '}
 "abcedefgh".unpack('B*')[0].gsub!(/../){|s| table[s]}.scan('dao').length

有1年没写ruby代码了，练习一下

very nice,very smart!

"youdao.com".unpack("B*").to_s.scan("dao".unpack("B*").to_s).size

PS:秦汉唐宋明的unpack("B*")很简洁。。
"youdao.com".unpack("C*").map{|x| "%08b" % x}.join也可以实现同样效果，不过罗嗦了点~

这里也有一个Base64编码相关的帖子：http://www.iteye.com/topic/286240

按照楼主的思路写了一个ruby版的实现:

def encode(str)
  keys = "abcdefghijklmnopqrstuvwxyz234567"
  str.unpack("C*").map{|b| "%08b" % b}.join.scan(/\d{1,5}/).map{|x| "0" * 3 + x.ljust(5,"0")}.map{|y| keys[y.to_i(2)].chr}.join
end

相比之下，googya的代码显得相当的笨拙！
部分原因是不熟悉unpack这个方法！用的是，最直接、最原始的想法

我发现我完全的错了。位数搞错了。我的方法，每个字符产生的只有7位，而应当是8位。

10 的 6 次方的字符串

凡是生成字符串，再去检查出dao字符串的，肯定都得超时

确实，这个问题都还没有考虑！！！

为了不超时,只能分段统计.
每段的连接处也要考滤10 00 01 .

public static void main(String[] args) {
List<String> lines = new ArrayList<String>();
char[] codes = new char[] { 'a', 'o', 'd', ' ' };
lines.add("www.youdao.com");
lines.add("dict.youdao.com");
for (String line : lines) {
if (line.length() == 0) {
continue;
}
int size = 0;
char[] queue = new char[] { ' ', ' ', ' ' };
int index = 0;
char[] chars = line.toCharArray();
for (int i = 0; i < chars.length; i++) {
queue[index] = codes[(chars[i] >>> 6) & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;

queue[index] = codes[(chars[i] >>> 4) & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;

queue[index] = codes[(chars[i] >>> 2) & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;

queue[index] = codes[chars[i] & 0x3];
index = (index + 1) % queue.length;
size += check(queue, index) ? 1 : 0;
}
System.out.println(size);
}
}

public static boolean check(char[] chars, int index) {
return chars[index] == 'd' && chars[(index + 1) % chars.length] == 'a'
&& chars[(index + 2) % chars.length] == 'o';
}

#写的有点复杂
按上面的思路不过还可以进行优化，比如可以按照KMP相关的思路减少check次数