轉(zhuǎn)載請(qǐng)注明出處：http://www.cnblogs.com/kirai/　作者：Kirai

零.問(wèn)題的提出

　　最近希望在分布式平臺(tái)上實(shí)現(xiàn)一個(gè)AC自動(dòng)機(jī)，但是如何在這樣的分布式平臺(tái)上表示這樣的非線性數(shù)據(jù)結(jié)構(gòu)就難住我了。因?yàn)橐恢痹谑褂肦DD提供的一些基本的操作，沒(méi)有需要什么復(fù)雜的操作。所以突然想到了在分布式的平臺(tái)上實(shí)現(xiàn)一個(gè)AC自動(dòng)機(jī)一定很有趣。網(wǎng)上搜了下，發(fā)現(xiàn)沒(méi)有人實(shí)現(xiàn)，因此決定嘗試實(shí)現(xiàn)?；蛟S就是一個(gè)玩具，不過(guò)也是能幫助自己更深理解分布式平臺(tái)上進(jìn)行編程和普通編程的區(qū)別吧。

　　這個(gè)問(wèn)題對(duì)我來(lái)講還是有一定的難度的，加上課業(yè)、復(fù)習(xí)考研、競(jìng)賽三重壓力，對(duì)于這個(gè)問(wèn)題的研究時(shí)間可能會(huì)比較長(zhǎng)，不過(guò)一定會(huì)抽出時(shí)間來(lái)考慮的。

　　文章僅僅是在記錄自己對(duì)問(wèn)題的思考過(guò)程和代碼，并不能保證每一步都是合理、有用、正確的。

一.實(shí)現(xiàn)可持久化字典樹(shù)

　　AC自動(dòng)機(jī)是個(gè)什么東西就不贅述了，我首先用python實(shí)現(xiàn)了一個(gè)比較樸素的版本，這里查詢(xún)是返回所有字典中出現(xiàn)的單詞的起始位置，每一個(gè)單詞一個(gè)list，最終組成一個(gè)dict。哈哈，也許有人看出來(lái)了這是去年的一道ICPC網(wǎng)賽題，沒(méi)錯(cuò)。但是我忘記是哪一道了，只記得當(dāng)時(shí)沒(méi)做出來(lái)，所以用python寫(xiě)一個(gè)就當(dāng)是對(duì)自己的一個(gè)補(bǔ)償吧：）

iOS培訓(xùn),Swift培訓(xùn),蘋(píng)果開(kāi)發(fā)培訓(xùn),移動(dòng)開(kāi)發(fā)培訓(xùn)

  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     """