MaxSize=100 #基于BF算法 def StrCount1(s,t): #BF算法求解 i,cnt=0,0 while i<len(s)-len(t)+1: j,k=i,0 while j<len(s) and k<len(t) and s[j]==t[k]: j,k=j+1,k+1 if k==len(t): #找到一个子串 cnt+=1 #累加出现的次数 i=j #i从j开始 else: i+=1 #i增加1 return cnt #基于KMP算法 def GetNext(t,next): #由模式串t求出next值
时间: 2023-12-12 17:05:13 浏览: 38
def GetNext(t, next):
next[0] = -1
i, j = 0, -1
while i < len(t) - 1:
if j == -1 or t[i] == t[j]:
i, j = i + 1, j + 1
next[i] = j
else:
j = next[j]
def StrCount2(s, t):
# KMP算法求解
i, j, cnt = 0, 0, 0
next = [-1] * len(t)
GetNext(t, next)
while i < len(s):
if j == -1 or s[i] == t[j]:
i, j = i + 1, j + 1
else:
j = next[j]
if j == len(t):
cnt += 1
j = 0
return cnt
相关问题
#include<iostream #define MAXSIZE 100 #define OK 1 #define ERROR 0 #define OVERFLOW -2 using namespa
#include<iostream>是C++中的一个预处理指令,它用于包含iostream头文件,该头文件中定义了输入输出流对象cin和cout,以及其他与输入输出相关的函数和类。
#define MAXSIZE 100是一个宏定义,它将MAXSIZE定义为100。宏定义是C++中的一种预处理指令,用于给常量或者函数起一个别名。
#define OK 1和#define ERROR 0是用于定义一些常量,OK表示操作成功,ERROR表示操作失败。
#define OVERFLOW -2也是用于定义一个常量,表示内存溢出。
using namespace std;是C++中的一个命名空间指令,它用于指定使用std命名空间中的标识符,这样就可以直接使用std命名空间中的标识符,而不需要加上std::前缀。
修改以下代码:MaxSize=20 #全局变量,假设容量为100 class CSqQueue1: #本例循环队列类 def __init__(self): #构造方法 self.data=[None]*MaxSize #存放队列中元素 self.rear=0 #队头指针 self.count=0 #队中元素个数 self.front = (self.rear - self.count + MaxSize) % MaxSize #队列的基本运算算法 def empty(self): #判断队列是否为空 return self.count==0 def push(self,e): #元素e进队 assert self.count!=MaxSize #检测队满 rear=(self.rear+1) % MaxSize self.data[rear]=e self.count+=1 #元素个数增1 def pop(self): # 出队元素 assert not self.empty() # 检测队空 self.count -= 1 # 元素个数减1 self.front = (self.rear - self.count + MaxSize) % MaxSize # 队头指针循环进1 return self.data[self.front] def gethead(self): # 取队头元素 assert not self.empty() # 检测队空 head = (self.front + 1) % MaxSize # 求队头元素的位置 return self.data[head] def size(self): # 返回队中元素个数 return ((self.rear - self.front + MaxSize) % MaxSize) #主程序 if __name__ == '__main__': st=CSqQueue1() st.push(7) st.push(5) st.push(10) st.push(3) print() print("队头元素: %d" % (st.gethead())) print(" 队列元素个数:%d" % (st.size())) print(" 出队元素:%d" % (st.pop())) print(" 队列元素个数:%d" % (st.size())) print()
MaxSize应该是100,而不是20。另外,队头指针的计算公式也需要修改为(self.rear - self.count + MaxSize) % MaxSize。修改后的代码如下:
```
MaxSize=100 #全局变量,假设容量为100
class CSqQueue1: #本例循环队列类
def __init__(self): #构造方法
self.data=[None]*MaxSize #存放队列中元素
self.rear=0 #队头指针
self.count=0 #队中元素个数
self.front = (self.rear - self.count + MaxSize) % MaxSize #队列的基本运算算法
def empty(self): #判断队列是否为空
return self.count==0
def push(self,e): #元素e进队
assert self.count!=MaxSize #检测队满
rear=(self.rear+1) % MaxSize
self.data[rear]=e
self.count+=1 #元素个数增1
def pop(self): # 出队元素
assert not self.empty() # 检测队空
self.count -= 1 # 元素个数减1
self.front = (self.rear - self.count + MaxSize) % MaxSize # 队头指针循环进1
return self.data[self.front]
def gethead(self): # 取队头元素
assert not self.empty() # 检测队空
head = (self.front + 1) % MaxSize # 求队头元素的位置
return self.data[head]
def size(self): # 返回队中元素个数
return ((self.rear - self.front + MaxSize) % MaxSize)
#主程序
if __name__ == '__main__':
st=CSqQueue1()
st.push(7)
st.push(5)
st.push(10)
st.push(3)
print()
print("队头元素: %d" % (st.gethead()))
print(" 队列元素个数:%d" % (st.size()))
print(" 出队元素:%d" % (st.pop()))
print(" 队列元素个数:%d" % (st.size()))
print()
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)