每日编程中遇到任何疑问、意见、建议请公众号留言或加入每日编程群聊739635399
输入个字符串，例如asdfghj，然后又给了个字符串，sdfg要求将输入字符串中的sdfg删除，就是相当于删除子字符串。
输入格式：
输入两个字符串，之间以空格隔开
输出格式：
删除子串后的字符串输入样例：
asdfghj sdfg输出样例：
ahj解决方法：
（1）算法的基本思想：
先找到子字符串，然后再进行删除操作，这里根据所学的数据结构存在两种方法，笔者先采用暴力法解决，KMP算法以注释给出。
（2）代码实现：
#include <iostream>
#include <string.h>
using namespace std;
//暴力搜索
int BF(char str[], char substr[])
{
//确定每个字符串的长度
int m = strlen(str);
int n = strlen(substr);
int i = 0, j = 0;
while (i < m && j < n)
{
if (str[i] == substr[j])
{ //若相等，则继续比较后序字符
i++;
j++;
}
else
{ //指针回退，重新匹配
i = i - j + 1;
j = 0;
}
}
if (j >= n)
return i - n;
else
return 0;
}
int length(char arr[], int pos, int pos1)
{
int slength = strlen(arr);
for (int i = pos1; i < slength; i++)
arr[pos++] = arr[i];
return pos;
}
//KMP算法求解
void getNext(char T[], int next[], int n)
{
int i = 1;
next[0] = 0; //不存储任何数据
next[1] = 0;
int j = 0;
while (i <= n)
{ //n表示字符串T的长度
if (j == 0 || T[i - 1] == T[j - 1])
{
i++;
j++;
next[i] = j;
}
else
j = next[j];
}
}
//KMP--求子串在主串中第pos个字符之后的位置的KMP算法
int KMP(char S[], char T[], int next[], int pos)
{
int i = pos;
int j = 1;
while (i <= strlen(S) && j <= strlen(T))
{
if (j == 0 || S[i - 1] == T[j - 1])
{
++i;
++j;
}
else
j = next[j];
}
if (j > strlen(T))
return i - strlen(T) - 1;
else
return 0;
}
int main()
{
cout << "输入两个字符串：" << endl;
//假设两个字符串的最大长度均为100
char str[100], substr[100];
cin >> str >> substr;
/*
KMP算法
int next[100];
getNext(substr, next, strlen(substr));
int pos = KMP(str, substr, next, 0);
*/
int pos = BF(str, substr);
int pos1 = pos + strlen(substr);
int lengthStr = length(str, pos, pos1);
for (int i = 0; i < lengthStr; i++)
cout << str[i];
system("pause");
return 0;
}
输入格式：
输入一个仅含字母的字符串
输出格式：
输出压缩后的字符串输入样例：
xxxxxdddfff输出样例：
x5d3f3