创建两个串,并采用顺序存储;实现串的插入、删除、求子串等基本操作。实现bf算法
时间: 2024-01-02 15:00:18 浏览: 125
数据结构C++ 串的基本操作和BF算法与KMP算法的比较—适合初学者和复习.docx
5星 · 资源好评率100%
顺序存储是一种将数据元素逐个存储在一块连续的存储空间中的方式。对于串的顺序存储,可以使用定长数组来实现。
首先创建两个定长数组作为串的存储空间,分别表示字符串s和t。
1. 串的插入:
在串s的第i个位置插入串t,需要将s[i...n]的元素后移m个位置,其中m为t的长度。然后将t的元素逐个赋值给s[i...i+m-1]的位置即可。
2. 串的删除:
删除串s的第i个位置开始长度为len的子串,需要将s[i+len...n]的元素前移len个位置。即将s[i+len]赋值给s[i],s[i+len+1]赋值给s[i+1],以此类推。
3. 求子串:
求串s中从第i个位置开始长度为len的子串,可以使用一个新的定长数组作为子串的存储空间,将s[i...i+len-1]的元素逐个赋值给子串的对应位置即可。
4. BF算法:
BF(Brute-Force)算法是一种简单粗暴的字符串匹配算法。它的基本思想是:从主串S的第一个字符开始,与模式串P的第一个字符比较,若相等则继续比较S的下一个字符与P的下一个字符,若不相等则主串S从下一个位置重新开始,与模式串P的第一个字符比较。如此循环下去,直到S的所有字符都与P相等,或者S已经没有字符可以比较。
具体实现时,可以用两个指针i和j,分别指向主串S和模式串P。在每一轮匹配时,若S[i]和P[j]相等,则i和j分别后移一位;若不相等,则i回退到上一轮匹配的下一个位置,j重新回到模式串P的第一个字符位置。
以上就是采用顺序存储实现串的插入、删除、求子串等基本操作,以及BF算法的实现。
阅读全文