设计顺序串的基本运算程序,并用相关数据进行测试。 其中串的模式匹配算法,对于输入的任意两个串:主串和子串,判断子串在主串中的位置。 如:主串为a b a b c a b,子串为abc,找输出其位置为3;若子串为abd,则提示子串在主串中不存在。
时间: 2023-12-06 18:44:19 浏览: 88
C语言C++数据结构课程设计 字符串的模式匹配(KMP算法与朴素算法).zip
以下是一个基本的顺序串运算程序,包括串的创建,串的输出,以及串的模式匹配算法:
```python
class SqString:
def __init__(self, maxsize):
self.maxsize = maxsize
self.data = [None] * self.maxsize
self.length = 0
def create(self, string):
self.length = len(string)
for i in range(self.length):
self.data[i] = string[i]
def output(self):
for i in range(self.length):
print(self.data[i], end='')
print()
def find(self, pattern):
n = self.length
m = len(pattern)
for i in range(n - m + 1):
if self.data[i:i+m] == pattern:
return i+1
return -1
```
使用示例:
```python
s = SqString(100)
s.create(['a', 'b', 'a', 'b', 'c', 'a', 'b'])
s.output() # 输出:ababcab
pos = s.find(['a', 'b', 'c'])
if pos == -1:
print('子串在主串中不存在')
else:
print('子串在主串中的位置为', pos) # 输出:子串在主串中的位置为 3
```
注意,这里的 `find` 方法采用的是暴力匹配算法,时间复杂度为 $O(nm)$,并不是最优的算法。如果需要更高效的算法可以考虑 KMP 算法或 Boyer-Moore 算法等。
阅读全文