首页 > 试题广场 >

小红的字符串修改

[编程题]小红的字符串修改

热度指数：7546 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

$\,\,\,\,\,\,\,\,\,\,$ 小红有一个由小写字母构成的字符串 $s$ ，每次她可以把其中一个任意一个字母替换成其在字母表中相邻的字母，例如把 ' $a$ ' 替换成 ' $b$ ' 或者 ' $z$ '。现在小红想知道，最少需要替换多少次，使得 $s$ 成为 $t$ 的子串。

$\,\,\,\,\,\,\,\,\,\,$ 如果字符串 $t$ 可以通过从字符串 $s$ 的开头删除若干（可能为零或全部）字符以及从结尾删除若干（可能为零或全部）字符得到，则字符串 $t$ 是字符串 $s$ 的子串。

输入描述:

第一行输入一个长度不超过  ，且仅由小写字母构成的字符串  代表小红手中待替换的串。
第二行输入一个长度不小于  但不超过  ，且仅由小写字母构成的字符串  代表目标串。

输出描述:

在一行上输出一个整数，代表最少需要替换的次数。

示例1

输入

abc
abbc

输出

说明

需要进行一次替换，将 '' 替换成 '' ，此时得到 "" ，是 "" 的子串，因为本质上是由 "" 末尾删除了一个字符得到的。

示例2

输入

zzzzzz
xyzabc

输出

算法知识视频讲解

牛客937233155号

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int min(char a,char b)
{
int dir= abs(a-b);
return dir < 26-dir ? dir : 26-dir;
}

int main() {
char s[1001];
char t[1001];
scanf("%s",&s);
scanf("%s",&t);
int len_s=strlen(s);
int len_t=strlen(t);

int num=10000;
for(int i=0;i<len_t-len_s;i++)
{
int sum=0;
for(int j=0;j<len_s;j++)
{
sum += min(s[j], t[i+j]);
}
if(sum<num)
{
num=sum;
}
}
printf("%d",num);
return 0;
}

发表于 2025-11-17 19:44:55 回复(0)