原文位于此處
http://bbs.jointforce.com/topic/19531
我似乎找到了一個(gè)O(m+n)的算法，同樣簡(jiǎn)潔但是沒(méi)有數(shù)字相乘造成太大數(shù)字的風(fēng)險(xiǎn)幸冻，無(wú)論多長(zhǎng)的兩個(gè)字符串，都只需要消耗一個(gè)8個(gè)字節(jié)的額外內(nèi)存用于計(jì)算。
簡(jiǎn)單的說(shuō)就是運(yùn)用位運(yùn)算，由于大小寫(xiě)字母總共有52個(gè)房铭，所以可用一個(gè)長(zhǎng)整型64位，每一位代表其中某一個(gè)字母温眉。先遍歷短字符串缸匪，對(duì)位掩碼進(jìn)行位設(shè)置操作，比如存在a則設(shè)置最低位為1芍殖。
然后遍歷長(zhǎng)字符串豪嗽，對(duì)每個(gè)字母所代表的位進(jìn)行清0谴蔑，比如存在a則設(shè)置最低位為0豌骏。
遍歷過(guò)后，如果64位長(zhǎng)整型仍然非0隐锭，則證明短字符串不是長(zhǎng)字符串的子集窃躲。
以上，敘述比較簡(jiǎn)單抽象…………實(shí)在是沒(méi)精神多寫(xiě)啊………………
