首页 > 试题广场 >

添加字符

[编程题]添加字符
  • 热度指数：450 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
牛牛手里有一个字符串A，羊羊的手里有一个字符串B，B的长度大于等于A，所以牛牛想把A串变得和B串一样长，这样羊羊就愿意和牛牛一起玩了。
而且A的长度增加到和B串一样长的时候，对应的每一位相等的越多，羊羊就越喜欢。比如"abc"和"abd"对应相等的位数为2，为前两位。
牛牛可以在A的开头或者结尾添加任意字符，使得长度和B一样。现在问牛牛对A串添加完字符之后，不相等的位数最少有多少位？

输入描述:
第一行为字符串A，第二行为字符串B，A的长度小于等于B的长度，B的长度小于等于50.字符均为小写字母。


输出描述:
输出一个整数表示A串添加完字符之后，不相等的位数最少有多少位？
示例1

输入

abe
cabc

输出

1
算法知识视频讲解
添加回答
十一月的may头像 十一月的may 
#include<iostream>
using namespace std;
int longestfix(string a, string b)
{
    int m=0;
    for(int j=0; j<=b.size()-a.size(); j++)
    {
        int num=0;
        for(int i=0; i<a.size(); i++)
            if(a[i]==b[i+j])
                num++;
        m=max(num,m);
    }
    return a.si***t main()
{
    string a,b;
    cin>>a>>b;
    cout<<longestfix(a,b)<<endl;
    return 0;
}



发表于 2021-08-12 14:59:04 回复(3)
C/C++
pein531头像 pein531
最开始想歪了，先动规求lcs再kmp求lcs在B中的所有位置，结果一直不对。实际上就是把A在B上滑窗，求窗口内两个字符串不同字符数的最小值，因为窗口之外的部分一定可以通过在A的两端追加和B相同的字符达到不增加不相等字符数的目的。 
#include <bits/stdc++.h>
using namespace std;

int main() {
    string A, B;
    cin >> A >> B;
    int n = A.size(), m = B.size();
    int ans = n;
    for(int left = 0; left <= m - n; left++) {
        int right = left + n - 1;
        int cnt = 0;
        for(int i = left; i <= right; i++) {
            cnt += A[i - left] != B[i];
        }
        ans = min(ans, cnt);
    }
    cout << ans << endl;
    return 0;
}
编辑于 2023-02-02 17:32:00 回复(0)
牛客991172186号头像 牛客991172186号
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
string a,b;
cin>>a>>b;
int maxlen=0;
for(int i=0;i<=b.size()-a.size();i++)
{int count=0;
 for(int k=0;k<a.size();k++)
 {if(a[k]==b[i+k]){count++;}}
 maxlen=max(count,maxlen);}
cout<<a.length()-maxlen<<endl;
return 0;}
发表于 2022-09-16 20:47:28 回复(0)
C/C++
break}头像 break}

C语言：滑动窗口法

1、滑动窗口并计数每次滑动的两字符串最大相同字符数，滑动（b字符长度-a字符长度+1）次；
2、输出（a字符长度-所有滑动次数中最大相同字符数）。

（运行时间3ms     占用内存344KB） 
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int main(void)
{
    int a=0,b=0;
    int maxlen=0,maxlen1=0;
    char *sa=(char*)malloc(sizeof(char)*100);
    char *sb=(char*)malloc(sizeof(char)*100);
    scanf("%s",sa);
    scanf("%s",sb);
    a=strlen(sa);
    b=strlen(sb);
    for(int i=0;i<b-a+1;i++)
    {
        maxlen1=0;
        for(int j=0;j<a;j++)
        {
            if(*(sa+j)==*(sb+i+j))
                maxlen1++;
        }
        maxlen=maxlen<maxlen1?maxlen1:maxlen;
    }
    printf("%d",a-maxlen);
    
    return 0;
}



发表于 2022-09-04 13:00:45 回复(0)
it`s_all_good_man头像 it`s_all_good_man

求大神搞个最优解啊！
小于O(n^2)的
编辑于 2021-10-20 13:52:18 回复(0)
牛客528470340号头像 牛客528470340号 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        int longs = longs(a, b);
        System.out.println(longs);

    }
    public static int longs(String a,String b){
        //转换为char类型数组
        char[] arrayA = a.toCharArray();
        char[] arrayB = b.toCharArray();
        int result=0;
        //字符a,b之间的差值
        for (int i = 0; i <= arrayB.length-arrayA.length; i++) {
            //对应位相等的个数
            int max=0;
            for (int j = 0; j < arrayA.length; j++) {
                //如果对应位相等
                if (arrayA[j]==arrayB[j+i]){
                    max++;
                }
            }
            result=Math.max(result,max);
        }
        return arrayA.length-result;
    }
}

发表于 2021-08-26 16:57:51 回复(1)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 安全工程师 游戏研发工程师 数据库工程师 信息技术岗 区块链 测试开发工程师 2020 大数据开发工程师 数据分析师 Java工程师 牛客
上传者：小小
难度：
6条回答 1997浏览

热门推荐

通过挑战的用户

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号