键盘读入主串S和模式串T,用BF(或KMP)算法判断模式串T是否为主串S的子串;用凯撒密码对模式串T加密,然后比较主串S和加密后的模式串T的大小
时间: 2024-05-03 14:19:04 浏览: 81
字符串的模式匹配详解--BF算法与KMP算法
5星 · 资源好评率100%
下面是用BF算法判断模式串T是否为主串S的子串的代码:
```python
def isSubstring(S, T):
n = len(S)
m = len(T)
for i in range(n-m+1):
j = 0
while j < m and S[i+j] == T[j]:
j += 1
if j == m:
return True
return False
```
其中,n为主串S的长度,m为模式串T的长度。如果找到了模式串T在主串S中的位置,就返回True;否则返回False。
接下来是用凯撒密码对模式串T加密,然后比较主串S和加密后的模式串T的大小的代码:
```python
def caesarCipher(T, k):
n = len(T)
res = ""
for i in range(n):
c = T[i]
if c.isalpha():
if c.islower():
res += chr((ord(c) - ord('a') + k) % 26 + ord('a'))
else:
res += chr((ord(c) - ord('A') + k) % 26 + ord('A'))
else:
res += c
return res
def compareStrings(S, T):
n = len(S)
m = len(T)
if n != m:
return False
for k in range(26):
if S == caesarCipher(T, k):
return True
return False
```
其中,caesarCipher函数用凯撒密码对模式串T加密,k为密钥;compareStrings函数比较主串S和加密后的模式串T的大小,如果相等就返回True,否则就返回False。
注意,在这个例子中,我们假设主串S和模式串T都是由英文字母和空格组成的字符串。如果需要处理其他字符集,需要做相应的修改。
阅读全文