首页 > 试题广场 >

添加字符

[编程题]添加字符

热度指数：3408 时间限制：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

输出

算法知识视频讲解

梦向南

#include<iostream>

#include<string.h>

using namespace std;

int CmpStr(char *strA, char *strB)

{

int cont = 0, max = 81;

int NA = strlen(strA), N = strlen(strB) - strlen(strA);

{

for (int i = 0; i < NA; i++)

{

if (strA[i] != strB[i + N])

cont++;

}

if (max > cont)

max = cont;

cont = 0;

} while (N--);

return max;

}

int main()

{

char strA[81], strB[81];

cin >> strA >> strB;

cout << CmpStr(strA, strB) << endl;

return 0;

}

发表于 2017-06-22 12:40:30 回复(0)

我犹豫了半天

就是求两个串的不一样的位数，，就是一个循环。

发表于 2017-10-27 22:03:33 回复(0)

被遗忘的左手

import java.util.*;
public class Main{
    public static void main(String[] args) {
        Scanner in = new  Scanner(System.in);
        String s1 = in.nextLine();
        String s2 = in.nextLine();
        int maxlen = 0;
        for(int i=0; i<=s2.length()-s1.length(); i++) {
            int count = 0;
            for(int j=0; j<s1.length(); j++) {
                if(s1.charAt(j) == s2.charAt(i+j)) {
                  count++;
                }
            }
            maxlen = Math.max(maxlen, count);
        }
        System.out.println(s1.length() - maxlen);
    }
}

编辑于 2017-05-26 11:14:07 回复(9)

Python

牛客341441072号

A = input()
B = input()
na,nb = len(A),len(B)
res = []
for i in range(nb-na+1):
    count = 0
    for j in range(na):
        if B[i+j]!=A[j]:
            count += 1
    res.append(count)
print(min(res))

发表于 2020-05-03 18:01:38 回复(1)

JavaScript

小儿比春花

var s1 = readline();
var s2 = readline();

if(s2.indexOf(s1) !== -1){
    print(0);
}
else{
    var c = [];
    for(var i = 0; i < s2.length - s1.length + 1; i++){
        var s11 = s2.slice(0, i) + s1 + s2.slice(i + s1.length);
        c.push(sameCount(s11, s2));
    }
    print(Math.min.apply(this, c));
}

function sameCount (a, b) {
    var count = 0;
    for(var i = 0; i < a.length; i++){
        if(a.charAt(i) == b.charAt(i)){
            count++;
        }
    }
    return a.length - count;
}

给JavaScript草存在感

发表于 2017-05-22 16:11:07 回复(2)

kylin小瓶子

哈哈哈，想说一个和答案无关的事情，牛牛一定很喜欢羊羊！他付出了那么多，搞个算法题，只为了让羊羊喜欢他😄😉

发表于 2020-04-09 11:22:45 回复(0)

Java

侬是一个好人

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        char[] a = in.next().toCharArray();
        char[] b = in.next().toCharArray();
        int m = a.length, n = b.length;

        //ret用于记录最终的最小差异数
        //初始化为m,即假设最坏情况是所有字符都不一样
        int ret = m;
        //外层循环：枚举字符串a在字符串b中的“起始对齐位置”
        //i表示a串对其到b串的第i个字符
        //判断条件i<=n-m保证了a串尾部不会越过b串的边界
        for(int i = 0; i <= n-m; i++){
            //tmp用于记录当前这次对齐中，有多少个字符不相同
            int tmp = 0;
            //内层循环：遍历字符串a的每一个字符
            for(int j = 0; j < m; j++){
                /**
                a[j]：a串的当前字符
                b[i+j]：b串的对应字符
                 */
                 if(a[j] != b[i+j]){
                    tmp++;
                 }
            }
            //每次内循环结束后，用当前算出的差异数tmp更新全局最小值ret
            ret = Math.min(ret,tmp);
        }
        System.out.println(ret);
    }
}

发表于 2025-11-24 12:30:04 回复(0)

浪味仙_

把这个短的字符串的起始位置向右挪动，求每次不同个数的最小值，两边不够的会补为相同的，所以不用考虑

#inclu把de <iostream>
#include <string>
using namespace std;

string s1, s2;

int main() 
{
    cin >> s1 >> s2;
    int n1 = s1.size();
    int n2 = s2.size();
    int ret = 51;
    for(int i = 0; i <= n2 - n1; i++)
    {
        int k = i, tmp = 0;
        for(int j = 0; j < n1; j++)
        {
            if(s1[j] != s2[k])
            {
                tmp++;
            }
            k++;
        }
        //cout << tmp << "  ";
        ret = min(ret, tmp);
    }
    cout << ret << endl;
    return 0;
}

发表于 2024-05-23 09:35:53 回复(0)

麦垛上的守望者

本质上就是求最大重合字符个数，除了短的字符串内部不能更换，两边的都可以添加成重复字符，所以结果就是len1-max

import java.util.Scanner;

public class Main3 {

    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);

        String s1=scanner.nextLine();
        String s2=scanner.nextLine();

        int len1=s1.length();
        int len2=s2.length();
        int count=0,max=0;

        for(int i=0;i<=len2-len1;i++){
            for(int j=0;j<len1;j++){
                if(s1.charAt(j)==s2.charAt(j+i))
                    count++;
            }
            if(max<count){
                max=count;
            }

            count=0;
        }

        System.out.println(len1-max);
        scanner.close();
    }
}

发表于 2018-05-15 10:46:35 回复(0)

逗比请来的猴子

import java.util.Scanner;

/*
 * 直接比较已有字符串中不相等的个数即可
 * */
public class MaxSameLen {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            String A = scanner.next();
            String B = scanner.next();

            int min = Integer.MAX_VALUE;
//            以A为模式串
            for (int i = 0; i <= B.length() - A.length(); i++) {
                int tmp = 0;
                for (int j = 0; j < A.length(); j++) {
                    if (A.charAt(j) != B.charAt(i + j)) {
                        tmp++;
                    }
                }
//                如果是子串的话，肯定为0
                min = Math.min(min, tmp);
                if (min == 0) {
                    break;
                }
            }
            System.out.println(min);
        }
    }


}
/*
adaabc
aababbc
2



* */

发表于 2018-04-05 17:16:01 回复(0)

小嗨喜欢在阳台看花海

<?php

$array[0]=str_split(trim(fgets(STDIN)));

$array[1]=str_split(trim(fgets(STDIN)));

$aa= [];

$cha= count($array[1])-count($array[0]);

for($i=0;$i<=$cha;$i++){

$aa[$i] = 0;

foreach($array[0] as$k=>$v){

if($v!= $array[1][$i+$k]) $aa[$i]++;

}

echomin($aa);

发表于 2018-03-22 17:46:00 回复(0)

牛客375006号

adaabc

aababbc

为什么输出是2？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

发表于 2017-10-20 04:26:13 回复(0)

牛客1050616号

#include<iostream>

#include<cstring>

using namespace std;

int main(){

char A[55],B[55];

cin>>A>>B;

int count=strlen(A);

int sum=0,t=0;

for(int i=0,j=0;i<strlen(B),j<strlen(A),t<=strlen(B)-strlen(A);i++,j++){

if(B[i]!=A[j]) sum++;

if(j==strlen(A)-1){

if(sum<count)count=sum;

i=i-j;

j=-1;

t++;

sum=0;

}

cout<<count<<endl;

}

编辑于 2017-09-08 16:54:12 回复(0)

牛客4425740号

python3

def least_different(a,b):
    la = len(a)
    lb = len(b)
    det = lb-la
    count_list = [0 for j in range(det+1)]
    for i in range(la):
        for j in range(det+1):
            if a[i] != b[i+j]:
                count_list[j] +=1
    return min(count_list)

a = input()
b = input()
print(least_different(a,b))

发表于 2017-09-07 16:04:11 回复(0)

南邮kd

import java.util.*;

public class Main {

public static void main(String[] args) {

// TODO Auto-generated method stub

Scanner sc=new Scanner(System.in);

while(sc.hasNext()){

String s1=sc.nextLine();

String s2=sc.nextLine();

int length=s2.length()-s1.length();

int maxCount=0;

for(int i=0;i<=length;i++){

int count=0;

for(int j=0;j<s1.length();j++){

if(s1.charAt(j)==s2.charAt(i+j)){

count++;

maxCount=(maxCount>count)?maxCount:count;

}

System.out.println(s1.length()-maxCount);

}

sc.close();

}

发表于 2017-08-20 11:57:49 回复(0)

OceanFan

import java.util.Scanner;

public class Main3 {

public static void main(String[] args) {

Scanner scanner=new Scanner(System.in);

String A=scanner.nextLine();

String B=scanner.nextLine();

scanner.close();

int m=A.length();

int n=B.length();

int count;

int maxLen=0;

for(int start=0,end=m;end<=n;start++,end++){

//依次从b中取与a等长的子串，判断子串中与a中重复字符个数，找到最大值即可

String BSubstring=B.substring(start, end);

count=0;

for(int i=0;i<m;i++){

if(A.charAt(i)==BSubstring.charAt(i)){

count++;

}

if(count>maxLen){

maxLen=count;

}

System.out.println(A.length()-maxLen);

}

发表于 2017-07-24 21:00:40 回复(0)

hanking

package 全国统一模拟第三场;

import java.util.Scanner;

public class Main_3 {
	
	public static void main(String[] args) {
		Scanner sc=new Scanner(System.in);
		while(sc.hasNext())
		{
			String str1=sc.next();
			String str2=sc.next();
			Max_diff(str1,str2);
		}
		sc.close();
	}
	public static void Max_diff(String str1,String str2)
	{
		int min_dif=Integer.MAX_VALUE;
		int diff=0;		
		for(int i=0;i<=str2.length()-str1.length();i++)
		{
			diff=diff_num(str1, str2.substring(i,i+str1.length()));
			min_dif=min_dif<diff?min_dif:diff;			
		}
		System.out.println(min_dif);
	}
	
	public static int  diff_char(String str1,String str2,int diff)
	{
		if(diff==0)
		{						
			return diff_num(str1, str2);
		}
		return Math.min(diff_char(str1, str2.substring(0, str2.length()-1),diff-1), diff_char(str1, str2.substring(1, str2.length()), diff-1));
	}
	public static int diff_num(String str1,String str2)
	{
		int res=0;
		for(int i=0;i<str1.length();i++)
		{
			if(str1.charAt(i)!=str2.charAt(i))
				res++;
		}
		return res;
	}
}

发表于 2017-07-19 22:14:55 回复(0)

Asdil

def f(a, b):
    a = '0' + a
    b = '0' + b
    la = len(a)
    lb = len(b)
    if la == lb:
        ret = 0
        for i in range(1, la):
            if a[i] == b[i]:
                ret += 1
        return la - 1 - ret
    dp = [[0]*lb for i in range(la)]
    for i in range(1, la):
        for j in range(i, lb-la+i+1):# 这一步很重要
            if a[i] == b[j]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = dp[i-1][j-1]
    ret = [max(dp[i]) for i in range(la)]
    ret = max(ret)
    return la - 1 - ret
 
if __name__ == '__main__':
    while 1:
        try:
            a = raw_input()
            b = raw_input()
        except:
            break
        print f(a, b)

发表于 2017-07-18 08:12:22 回复(0)

风萧萧梦也潇潇


	//我的思路是：将a和取长度为（a的长度）的b的连续子串作比较，看每次比较的相应位置的不同字符的个数，求最小值



	let a=readline()



	let b=readline()



	let diff=function(a,b){



	let l=a.length



	let num=0



	for(let i=0;i<l;i++){



	if(a[i]!==b[i])num++;



	}



	return num;



	}



	let al=a.length;



	let min=al;



	for(let i=0,bl=b.length;i<=bl-al;i++){



	let r=diff(a,b.slice(i))



	if(min>r)min=r



	}



	print(min)