【每日编程-25期】LZ上机题(一)

输入个字符串，例如asdfghj，然后又给了个字符串，sdfg要求将输入字符串中的sdfg删除，就是相当于删除子字符串。

asdfghj sdfg

ahj

解决方法：

（1）算法的基本思想：

先找到子字符串，然后再进行删除操作，这里根据所学的数据结构存在两种方法，笔者先采用暴力法解决，KMP算法以注释给出。

（2）代码实现：

#include<iostream>#include<string.h>usingnamespacestd;//暴力搜索intBF(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;elsereturn0;}intlength(char arr[], int pos, int pos1){int slength = strlen(arr);for (int i = pos1; i < slength; i++)        arr[pos++] = arr[i];return pos;}//KMP算法求解voidgetNext(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算法intKMP(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;elsereturn0;}intmain(){cout << "输入两个字符串：" << endl;//假设两个字符串的最大长度均为100char 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");return0;}

输入格式：

输入一个仅含字母的字符串

输出格式：

输入样例：

xxxxxdddfff

输出样例：

x5d3f3