使用C++语言编程,串的模式匹配,设s,t为两个字符串,判断t是否为s的子串,如果是,输出子串所在位置(第一个字符),否则输出-1.根据位置和长度,删除子串
时间: 2024-05-26 11:10:03 浏览: 84
c/c++程序之_KMP字符串模式匹配详解
可以使用 KMP 算法来实现字符串的模式匹配,该算法的时间复杂度为 O(m+n),其中 m 和 n 分别表示 s 和 t 的长度。
以下是实现代码:
#include <stdio.h>
#include <string.h>
void getNext(char *t, int *next)
{
int i = 0, j = -1;
next[0] = -1;
while (i < strlen(t))
{
if (j == -1 || t[i] == t[j])
{
i++;
j++;
next[i] = j;
}
else
{
j = next[j];
}
}
}
int kmp(char *s, char *t, int *next)
{
int i = 0, j = 0;
while (i < strlen(s) && j < strlen(t))
{
if (j == -1 || s[i] == t[j])
{
i++;
j++;
}
else
{
j = next[j];
}
}
if (j == strlen(t))
{
return i-j;
}
else
{
return -1;
}
}
int main()
{
char s[100], t[100];
int next[100];
printf("请输入字符串 s:");
scanf("%s", s);
printf("请输入字符串 t:");
scanf("%s", t);
getNext(t, next);
int pos = kmp(s, t, next);
if (pos == -1)
{
printf("%s 不是 %s 的子串。\n", t, s);
}
else
{
printf("%s 是 %s 的子串,位置为 %d,长度为 %d。\n", t, s, pos+1, strlen(t));
memmove(s+pos, s+pos+strlen(t), strlen(s)-pos-strlen(t)+1);
printf("删除子串后的字符串为 %s。\n", s);
}
return 0;
}
其中,getNext 函数用于计算 t 的前缀后缀相同的最长长度数组 next,kmp 函数用于在 s 中查找 t 的位置。查找成功时返回子串起始位置 pos,将 pos 及其之后的字符串往前移动 strlen(t) 个位置即可实现删除子串的功能。
阅读全文