转载请注明出处：http://www.cnblogs.com/kirai/ 作者：Kirai
零.问题的提出
最近希望在分布式平台上实现一个AC自动机，但是如何在这样的分布式平台上表示这样的非线性数据结构就难住我了。因为一直在使用RDD提供的一些基本的操作，没有需要什么复杂的操作。所以突然想到了在分布式的平台上实现一个AC自动机一定很有趣。网上搜了下，发现没有人实现，因此决定尝试实现。或许就是一个玩具，不过也是能帮助自己更深理解分布式平台上进行编程和普通编程的区别吧。
这个问题对我来讲还是有一定的难度的，加上课业、复习考研、竞赛三重压力，对于这个问题的研究时间可能会比较长，不过一定会抽出时间来考虑的。
文章仅仅是在记录自己对问题的思考过程和代码，并不能保证每一步都是合理、有用、正确的。
一.实现可持久化字典树
AC自动机是个什么东西就不赘述了，我首先用python实现了一个比较朴素的版本，这里查询是返回所有字典中出现的单词的起始位置，每一个单词一个list，最终组成一个dict。哈哈，也许有人看出来了这是去年的一道ICPC网赛题，没错。但是我忘记是哪一道了，只记得当时没做出来，所以用python写一个就当是对自己的一个补偿吧：）
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 """
