字符串采用顺序存储结构,设计求子串的算法;
时间: 2024-05-08 15:19:06 浏览: 65
字符串算法
3星 · 编辑精心推荐
假设原字符串为str,子串为substr,其长度为len_sub。
1. 首先判断substr的长度是否小于等于str的长度,如果不是,则不存在子串,直接返回空。
2. 然后从str的第一个字符开始遍历,以当前字符作为子串的起始字符,判断接下来的len_sub个字符是否与substr相同。
3. 如果相同,则找到了一个子串,记录其起始位置并将其存入结果数组中。
4. 如果不同,则继续遍历str的下一个字符,以此类推直到遍历完整个字符串。
5. 最后返回结果数组,即为所有子串的起始位置。
代码实现如下:
```
vector<int> findSubstr(string str, string substr) {
vector<int> res;
int len_str = str.length(), len_sub = substr.length();
if (len_sub > len_str) return res;
for (int i = 0; i <= len_str - len_sub; i++) {
bool flag = true;
for (int j = 0; j < len_sub; j++) {
if (str[i+j] != substr[j]) {
flag = false;
break;
}
}
if (flag) res.push_back(i);
}
return res;
}
```
阅读全文