轉(zhuǎn)載請注明出處：http://www.cnblogs.com/kirai/ 作者：Kirai
零.問題的提出
最近希望在分布式平臺(tái)上實(shí)現(xiàn)一個(gè)AC自動(dòng)機(jī)，但是如何在這樣的分布式平臺(tái)上表示這樣的非線性數(shù)據(jù)結(jié)構(gòu)就難住我了。因?yàn)橐恢痹谑褂肦DD提供的一些基本的操作，沒有需要什么復(fù)雜的操作。所以突然想到了在分布式的平臺(tái)上實(shí)現(xiàn)一個(gè)AC自動(dòng)機(jī)一定很有趣。網(wǎng)上搜了下，發(fā)現(xiàn)沒有人實(shí)現(xiàn)，因此決定嘗試實(shí)現(xiàn)?；蛟S就是一個(gè)玩具，不過也是能幫助自己更深理解分布式平臺(tái)上進(jìn)行編程和普通編程的區(qū)別吧。
這個(gè)問題對我來講還是有一定的難度的，加上課業(yè)、復(fù)習(xí)考研、競賽三重壓力，對于這個(gè)問題的研究時(shí)間可能會(huì)比較長，不過一定會(huì)抽出時(shí)間來考慮的。
文章僅僅是在記錄自己對問題的思考過程和代碼，并不能保證每一步都是合理、有用、正確的。
一.實(shí)現(xiàn)可持久化字典樹
AC自動(dòng)機(jī)是個(gè)什么東西就不贅述了，我首先用python實(shí)現(xiàn)了一個(gè)比較樸素的版本，這里查詢是返回所有字典中出現(xiàn)的單詞的起始位置，每一個(gè)單詞一個(gè)list，最終組成一個(gè)dict。哈哈，也許有人看出來了這是去年的一道ICPC網(wǎng)賽題，沒錯(cuò)。但是我忘記是哪一道了，只記得當(dāng)時(shí)沒做出來，所以用python寫一個(gè)就當(dāng)是對自己的一個(gè)補(bǔ)償吧：）
1 # -*- coding: utf-8 -*- 2 class Node: 3 """ 4 A Trie's basic data structure. 5 """ 6 def __init__(self): 7 self.next_letter = {} 8 self.is_word = False 9 self.letter = '' 10 self.depth = -1 11 self.pre = None 12 self.fail = None 13 14 15 class Trie: 16 def __init__(self): 17 self.root = Node() 18 19 20 def insert(self, word): 21 """
