串是一种常见的数据结构，这里使用Python定义类来实现相应的方法。先看代码，再对相关知识进行讲解。
1 # coding=utf-8
2
3 __all__=['ADTString']
4
5 class ADTString(object):
6     '''
7     此类用于描述串，包含以下方法
8     '''
9     def __init__(self， d=''):
10         '''
11         data用于存储串
12         '''
13         self.data = d
14
15     def StrCopy(self):
16         '''
17         复制函数，返回主串data
18         '''
19         return self.data
20
21     def ClearString(self):
22         '''
23         清空主串
24         '''
25         self.data = ''
26
27     def StringEmpty(self):
28         '''
29         判断主串是否为空，返回True或False
30         '''
31         return False if len(self.data) else True
32
33     def StrLength(self):
34         '''
35         返回主串的长度
36         '''
37         return len(self.data)
38
39     def StrCompare(self， T):
40         '''
41         主串和串T进行比较，大于串T返回1，等于串T返回0，小于串T返回-1
42         '''
43         len_S = self.StrLength()
44         len_T = T.StrLength()
45         len_min = min(len_S， len_T)
46         len_max = max(len_S， len_T)
47         i=j=0
48         while(True):
49             if (i>=len_min):
50                 if len_min==len_max:
51                     return 0
52                 elif (j >=len_min):
53                     return 1 if len_S  > len_T else -1
54
55             if(self.data[i]==T.data[j]):
56                 i=i+1
57                 j=j+1
58             elif self.data[i]<T.data[j]:
59                 return -1
60             elif self.data[i]>T.data[j]:
61                 return 1
62
63     def Concat(self， S2):
64         '''
65         拼接主串和串S2
66         '''
67         return self.data+S2.data
68
69     def SubString(self， pos， len_):
70         '''
71         返回主串中，第pos个字符后len_长的子串
72         pos为负数，则逆序
73         '''
74         if pos >= 0:
75             if len(self.data) < pos:
76                 return -1
77             return self.data[pos:pos+len_]
78         else:
79             if len_==0 or pos==-1:
80                 return ''
81             elif pos+len_==0 or abs(pos)<len_:
82                 return self.data[pos:-1]+self.data[-1]
83             else:
84                 return self.data[pos:pos+len_]
85
86     def Index(self， T， pos):
87         '''
88         若主串S中存在和串T值相同的子串，则返回它在主串中第pos个字符之后第一次出现的位置，否则返回-1
89         '''
90         len_T = T.StrLength()
91         len_S = self.StrLength()
92         if len_S < len_T + pos:
93             return -1
94
95         p1 = pos
96         p2 = pos + len_T
97         while(p2<=len_S):
98             if self.SubString(p1， len_T) == T.data:
99                 return p1
100             else:
101                 p1=p1+1
102                 p2=p2+1
103
104         if p2 > len_S:
105             return -1
106
107     def IndexBruteforce(self， T， pos):
108         '''
109         朴素匹配算法，若主串S中存在和串T值相同的子串，则返回它在主串中第pos个字符之后第一次出现的位置，否则返回-1；不使用串定义的方法来实现
110         '''
111         len_T = T.StrLength()
112         len_S = self.StrLength()
113         i=pos
114         j=0
115         while(True):
116             if i >= len_S or j >= len_T:
117                 break
118             if(self.data[i]==T.data[j]):
119                 i=i+1
120                 j=j+1
121             else:
122                 i=i-j+1
123                 j=0
124
125         return i-j if j>=len_T else -1
126
127     def GetNext(self):
128         '''
129         返回KMP匹配算法所需的next数组
130         '''
131         len_S=self.StrLength()
132         next=[0]
133         i=1
134         while(True):
135             if i>=len_S:
136                 break
137
138             k = next[i-1]
139             while(self.data[k]!=self.data[i] and k!=0):
140                 k=next[k-1]
141             if self.data[k]==self.data[i]:
142                 next.append(k+1)
143             else:
144                 next.append(0)
145
146             i=i+1
147         return next
148
149     def IndexKMP(self， T， pos):
150         '''
151         KMP匹配算法，若主串S中存在和串T值相同的子串，则返回它在主串中第pos个字符之后第一次出现的位置，否则返回-1；不使用串定义的方法来实现
152         '''
153         next=self.GetNext()
154         len_T = T.StrLength()
155         len_S = self.StrLength()
156         i=pos
157         j=0
158         while(True):
159             if i >= len_S or j >= len_T:
160                 break
161             if(self.data[i]==T.data[j]):
162                 i=i+1
163                 j=j+1
164             else:
165                 i=i+next[i]+1
166                 j=0
167         return i-j if j>=len_T else -1
168
169
170
171     def Replace(self， T， V):
172         '''
173         用串V替换主串S中，出现的所有与串T相等的不重叠的子串
174         '''
175         string = ''
176         len_S = len(self.data)
177         len_T = len(T.data)
178         p1=p2=0
179         while(True):
180             pos = self.Index(T， p2)
181             if pos == -1:
182                 string+=self.data[p2:]
183                 break
184             else:
185                 p1=pos
186                 string+=self.data[p2:p1]
187                 string+= V.data
188                 p2=p1+len_T
189
190         if string == '':
191             return self.data
192         else:
193             return string
194
195     def StrInsert(self， pos， T):
196         '''
197         在主串的第pos个字符后，插入串T;pos为负，则逆序插入
198         '''
199         len_S = len(self.data)
200         if len_S < pos or len_S <abs(pos):
201             return -1
202
203         return self.data[:pos]+T.data+self.data[pos:]
204
205     def StrDelete(self， pos， len_):
206         '''
207         在主串的第pos个字符后，删除len_长度的字符
208         pos小于0则逆序删除
209         '''
210         len_S = len(self.data)
211         if pos >= 0:
212             if len_S < pos:
213                 return -1
214             return self.data[:pos]+self.data[pos+len_:]
215         else:
216             if len_S < abs(pos) :
217                 return -1
218             return self.data[:pos-len_]+self.data[pos:]
219
220 if __name__ == '__main__':
221     from ADTString import ADTString
222     # 打印该类的readme文档
223     print help(ADTString)
　　第3行：__all__中定义的内容，是使用from <module> import * 时，会导出的内容。
　　第15~218行：串的一些基本方法，其中，第86~105行的Index，是使用到串SubString方法来实现的；第107~125行，是使用朴素匹配算法实现的；第149~167行，是使用KMP匹配算法来实现的。
　　第223行：是打印根据代码和注释，自动生成的参考文档。
　　下面对这个类进行单元测试，使用unittest模块，代码的后两行，是执行单元测试的意思。
1 # conding=utf-8
2
3 from ADTString import ADTString
4 import unittest
5
6 class TestADTStringMethods(unittest.TestCase):
7     def setUp(self):
8         self.obj = ADTString()
9
10     def tearDown(self):
11         pass
12
13     def test_StrCopy(self):
14         self.obj.data=''
15         self.assertEqual(self.obj.StrCopy()， '')
16         self.obj.data='goodgoogle'
17         self.assertEqual(self.obj.StrCopy()， 'goodgoogle')
18         self.obj.data='!'
19         self.assertEqual(self.obj.StrCopy()， '!')
20
21     def test_ClearString(self):
22         self.obj.data='goodgoogle'
23         self.obj.ClearString()
24         self.assertEqual(self.obj.data， '')
25
26     def test_StringEmpty(self):
27         self.obj.data=''
28         self.assertEqual(self.obj.data， '')
29
30     def test_StrLength(self):
31         self.obj.data='123'
32         self.assertEqual(self.obj.StrLength()， 3)
33         self.obj.data=''
34         self.assertEqual(self.obj.StrLength()， 0)
35
36     def test_StrCompare(self):
37         obj_T=ADTString('goodgoogle')
38         self.obj.data='goodgoogle'
39         self.assertEqual(self.obj.StrCompare(obj_T)，0)
40         self.obj.data='goodgoogl'
41         self.assertEqual(self.obj.StrCompare(obj_T)，-1)
42         self.obj.data='goodgooglea'
43         self.assertEqual(self.obj.StrCompare(obj_T)，1)
44
45     def test_Concat(self):
46         self.obj.data='good'
47         obj_S2=ADTString('google')
48         self.assertEqual(self.obj.Concat(obj_S2)，'goodgoogle')
49         self.obj.data=''
50         self.assertEqual(self.obj.Concat(obj_S2)，'google')
51
52     def test_SubString(self):
53         self.obj.data='goodgoogle'
54         self.assertEqual(self.obj.SubString(0，0)，'')
55         self.assertEqual(self.obj.SubString(0，1)，'g')
56         self.assertEqual(self.obj.SubString(0，4)，'good')
57         self.assertEqual(self.obj.SubString(0，100)，'goodgoogle')
58         self.assertEqual(self.obj.SubString(100，1)，-1)
59         self.assertEqual(self.obj.SubString(-50，0)，'')
60         self.assertEqual(self.obj.SubString(-5，0)，'')
61         self.assertEqual(self.obj.SubString(-1，0)，'')
62         self.assertEqual(self.obj.SubString(-1，1)，'')
63         self.assertEqual(self.obj.SubString(-1，2)，'')
64         self.assertEqual(self.obj.SubString(-6，1)，'g')
65         self.assertEqual(self.obj.SubString(-6，6)，'google')
66         self.assertEqual(self.obj.SubString(-6，100)，'google')
67         self.assertEqual(self.obj.SubString(-6，10)，'google')
68
69     def test_Index(self):
70         self.obj.data='goodgoogle'
71         obj_T=ADTString('good')
72         self.assertEqual(self.obj.Index(obj_T， 0)，0)
73         self.assertEqual(self.obj.Index(obj_T， 1)，-1)
74         self.obj.data='googlegood'
75         self.assertEqual(self.obj.Index(obj_T， 0)，6)
76         self.assertEqual(self.obj.Index(obj_T， 7)，-1)
77         self.obj.data=''
78         self.assertEqual(self.obj.Index(obj_T， 0)，-1)
79
80     def test_IndexBruteforce(self):
81         self.obj.data='goodgoogle'
82         obj_T=ADTString('good')
83         self.assertEqual(self.obj.Index(obj_T， 0)，0)
84         self.assertEqual(self.obj.Index(obj_T， 1)，-1)
85         self.obj.data='googlegood'
86         self.assertEqual(self.obj.Index(obj_T， 0)，6)
87         self.assertEqual(self.obj.Index(obj_T， 7)，-1)
88         self.obj.data=''
89         self.assertEqual(self.obj.Index(obj_T， 0)，-1)
90
91     def test_IndexKMP(self):
92         self.obj.data='goodgoogle'
93         obj_T=ADTString('good')
94         self.assertEqual(self.obj.Index(obj_T， 0)，0)
95         self.assertEqual(self.obj.Index(obj_T， 1)，-1)
96         self.obj.data='googlegood'
97         self.assertEqual(self.obj.Index(obj_T， 0)，6)
98         self.assertEqual(self.obj.Index(obj_T， 7)，-1)
99         self.obj.data=''
100         self.assertEqual(self.obj.Index(obj_T， 0)，-1)
101
102     def test_Replace(self):
103         self.obj.data='good'
104         obj_T=ADTString('good')
105         obj_V=ADTString('replace')
106         self.assertEqual(self.obj.Replace(obj_T， obj_V)，'replace')
107         self.obj.data='googlegood'
108         self.assertEqual(self.obj.Replace(obj_T， obj_V)，'googlereplace')
109         self.obj.data='goodgooglegood'
110         self.assertEqual(self.obj.Replace(obj_T， obj_V)，'replacegooglereplace')
111         self.obj.data=''
112         self.assertEqual(self.obj.Replace(obj_T， obj_V)，'')
113         self.obj.data='aaa'
114         self.assertEqual(self.obj.Replace(obj_T， obj_V)，'aaa')
115
116     def test_StrInsert(self):
117         self.obj.data='goodgoogle'
118         obj_T=ADTString('insert')
119         self.assertEqual(self.obj.StrInsert(0，obj_T)，'insertgoodgoogle')
120         self.assertEqual(self.obj.StrInsert(100，obj_T)，-1)
121         self.assertEqual(self.obj.StrInsert(len(self.obj.data)，obj_T)，'goodgoogleinsert')
122         self.assertEqual(self.obj.StrInsert(4，obj_T)，'goodinsertgoogle')
123         self.assertEqual(self.obj.StrInsert(-1，obj_T)，'goodgooglinserte')
124         self.assertEqual(self.obj.StrInsert(-100，obj_T)，-1)
125
126     def test_StrDelete(self):
127         self.obj.data='goodgoogle'
128         self.assertEqual(self.obj.StrDelete(0，4)，'google')
129         self.assertEqual(self.obj.StrDelete(0，100)，'')
130         self.assertEqual(self.obj.StrDelete(-1，1)，'goodgooge')
131         self.assertEqual(self.obj.StrDelete(-2，3)，'goodgle')
132         self.assertEqual(self.obj.StrDelete(-2，100)，'le')
133         self.assertEqual(self.obj.StrDelete(-100，1)，-1)
134
135
136 suite = unittest.TestLoader().loadTestsFromTestCase(TestADTStringMethods)
137 unittest.TextTestRunner(verbosity=2).run(suite)
　　执行的结果如下：
test_ClearString (__main__.TestADTStringMethods) ... ok
test_Concat (__main__.TestADTStringMethods) ... ok
test_Index (__main__.TestADTStringMethods) ... ok
test_IndexBruteforce (__main__.TestADTStringMethods) ... ok
test_IndexKMP (__main__.TestADTStringMethods) ... ok
test_Replace (__main__.TestADTStringMethods) ... ok
test_StrCompare (__main__.TestADTStringMethods) ... ok
test_StrCopy (__main__.TestADTStringMethods) ... ok
test_StrDelete (__main__.TestADTStringMethods) ... ok
test_StrInsert (__main__.TestADTStringMethods) ... ok
test_StrLength (__main__.TestADTStringMethods) ... ok
test_StringEmpty (__main__.TestADTStringMethods) ... ok
test_SubString (__main__.TestADTStringMethods) ... ok
----------------------------------------------------------------------
Ran 13 tests in 0.001s
OK
[Finished in 0.1s]