1 #!/urs/bin/env python
  2 # -*- coding:utf-8 -*-
  3 
  4 #异常类
  5 class stringTypeError(TypeError):
  6     pass
  7 
  8 #节点类
  9 class Node(object):
 10     def __init__(self, elem, next_ = None):
 11         self.elem = elem
 12         self.next = next_
 13 #单链表类
 14 class single_list(object):
 15     def __init__(self):
 16         self._head = None
 17         self._num  = 0
 18 
 19     def __len__(self):
 20         return self._num
 21 
 22     def prepend(self,elem):
 23         self._head = Node(elem, self._head)
 24         self._num += 1
 25 
 26     def append(self,elem):
 27         if self._head is None:
 28             self._head = Node(elem)
 29             self._num += 1
 30             return
 31         p = self._head
 32         while p.next:
 33             p = p.next
 34         p.next = Node(elem)
 35         self._num += 1
 36 
 37     def pop_last(self):
 38         if self._head is None:
 39             raise ValueError("in pop_last")
 40         p = self._head
 41         if p.next is None:
 42             e = p.elem
 43             self._head = None
 44             self._num -= 1
 45             return e
 46         while p.next.next:
 47             p = p.next
 48         e = p.next.elem
 49         p.next = None
 50         self._num -= 1
 51         return e
 52 
 53     def delitem(self, key):
 54         if key == len(self)-1:
 55             self.pop_last()
 56         elif 0<= key < len(self) - 1:
 57             p = self._head
 58             pre = None
 59             num = -1
 60             while p is not None:
 61                 num += 1
 62                 if key==num:
 63                     if not pre:
 64                         self._head = p.next
 65                         self._num -= 1
 66                     else:
 67                         pre.next = p.next
 68                         self._num -= 1
 69                     break
 70                 else:
 71                     pre = p
 72                     p = p.next
 73         else:
 74             raise IndexError
 75 
 76     def insert(self, key, elem):
 77         if key>=len(self)-1:
 78             self.append(elem)
 79         elif 0<=key<len(self)-1:
 80             p = self._head
 81             pre = None
 82             num = -1
 83             while p:
 84                 num += 1
 85                 if num==key:
 86                     if not pre:
 87                         self._head = Node(elem, self._head)
 88                         self._num += 1
 89                     else:
 90                         pre.next = Node(elem, pre.next)
 91                         self._num += 1
 92                     break
 93                 else:
 94                     pre = p
 95                     p = p.next
 96         else:
 97             raise IndexError
 98 
 99     # 打印显示
100     def printall(self):
101         p = self._head
102         while p:
103             print(p.elem, end="")
104             if p.next:
105                 print(", ", end="")
106             p = p.next
107         print("")
108 
109 
110 #单链表字符串类
111 class string(single_list):
112     def __init__(self, value):
113         self.value =http://www.mamicode.com/ str(value)
114         single_list.__init__(self)
115         for i in range(len(self.value)-1,-1,-1):
116             self.prepend(self.value[i])
117 
118     def length(self):
119         return self._num
120 
121     def printall(self):
122         p = self._head
123         print("字符串结构：",end="")
124         while p:
125             print(p.elem, end="")
126             if p.next:
127                 print("-->", end="")
128             p = p.next
129         print("")
130 
131     #朴素的串匹配算法，返回匹配的起始位置
132     def naive_matching(self, p):  #self为目标字符串，t为要查找的字符串
133         if not isinstance(self, string) and not isinstance(p, string):
134             raise stringTypeError
135         m, n = p.length(), self.length()
136         i, j = 0, 0
137         while i < m and j < n:
138             if p.value[i] == self.value[j]:#字符相同，考虑下一对字符
139                 i, j = i+1, j+1
140             else:               #字符不同，考虑t中下一个位置
141                 i, j = 0, j-i+1
142         if i == m:              #i==m说明找到匹配,返回其下标
143             return j-i
144         return -1
145 
146     #kmp匹配算法，返回匹配的起始位置
147     def matching_KMP(self, p):
148         j, i = 0, 0
149         n, m = self.length(), p.length()
150         while j < n and i < m:
151             if i == -1 or self.value[j] == p.value[i]:
152                 j, i = j + 1, i + 1
153             else:
154                 i = string.gen_next(p)[i]
155         if i == m:
156             return j - i
157         return -1
158 
159     # 生成pnext表
160     @staticmethod
161     def gen_next(p):
162         i, k, m = 0, -1, p.length()
163         pnext = [-1] * m
164         while i < m - 1:
165             if k == -1 or p.value[i] == p.value[k]:
166                 i, k = i + 1, k + 1
167                 pnext[i] = k
168             else:
169                 k = pnext[k]
170         return pnext
171 
172     #把old字符串出现的位置换成new字符串
173     def replace(self, old, new):
174         if not isinstance(self, string) and not isinstance(old, string) 175                 and not isinstance(new, string):
176             raise stringTypeError
177 
178         #删除匹配的旧字符串
179         start = self.matching_KMP(old)
180         for i in range(old.length()):
181             self.delitem(start)
182         #末尾情况下时append追加的，顺序为正；而前面的地方插入为前插；所以要分情况
183         if start<self.length():
184             for i in range(new.length()-1, -1, -1):
185                 self.insert(start,new.value[i])
186         else:
187             for i in range(new.length()):
188                 self.insert(start,new.value[i])
189 
190 
191 if __name__=="__main__":
192 
193     a = string("abcda")
194     print("字符串长度：",a.length())
195     a.printall()
196     b = string("abcabaabcdabdabcda")
197     print("字符串长度：", b.length())
198     b.printall()
199     print("朴素算法_匹配的起始位置：",b.naive_matching(a),end=" ")
200     print("KMP算法_匹配的起始位置：",b.matching_KMP(a))
201     c = string("xu")
202     print("==")
203     b.replace(a,c)
204     print("替换后的字符串是：")
205     b.printall()