首页 > 试题广场 >

字符串问题

[编程题]字符串问题

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

小摩手里有一个字符串A，小拜的手里有一个字符串B，B的长度大于等于A，所以小摩想把A串变得和B串一样长，这样小拜就愿意和小摩一起玩了。

而且A的长度增加到和B串一样长的时候，对应的每一位相等的越多，小拜就越喜欢。比如"abc"和"abd"对应相等的位数为2，为前两位。

小摩可以在A的开头或者结尾添加任意字符，使得长度和B一样。现在问小摩对A串添加完字符之后，不相等的位数最少有多少位？

输入描述:

第一行 为字符串A，第二行 为字符串B，
A的长度小于等于B的长度，B的长度小于等于100。
字符均为小写字母。

输出描述:

输出一行整数表示A串添加完字符之后，A B 不相等的位数最少有多少位？

示例1

输入

abe
cabc

输出

算法知识视频讲解

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] a = br.readLine().toCharArray();
        char[] b = br.readLine().toCharArray();

        int n = b.length - a.length;
        int res = Integer.MAX_VALUE;
        for (int i = 0; i <= n; i++) {
            int count = 0;
            for (int j = 0; j < a.length; j++) {
                if (a[j] != b[j + i]) count++;
            }
            res = Math.min(res, count);
        }
        System.out.println(res);
    }
}

发表于 2019-01-18 16:34:35 回复(0)

无心2019

#include <bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;
    cin>>a;
    cin>>b;
    int n1=0,n2=0,n=0;
    for(int i=0;i<a.size();i++)
    {
        if(a[i]==b[i])
            n1++;
        if(a[i]==b[i+b.size()-a.size()])
            n2++;
    }
    cout<<a.size()-max(n1,n2)<<endl;
    return 0;
}

发表于 2019-06-19 21:15:06 回复(3)

向宇回桌

import java.util.*;

public class Main {
    private static final int INT_MAX = 0X3f3f3f3f;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.next().toCharArray(), b = sc.next().toCharArray();
        int ans = INT_MAX;
        for (int i=0; i<=b.length-a.length; i++) {
            int diff = 0;
            for (int j=0; j!=a.length; j++) {
                if (a[j] != b[i+j]) { diff++; }
            }
            ans = Math.min(diff, ans);
        }
        System.out.println(ans);
    }
}

发表于 2019-02-15 11:29:40 回复(2)

J.Fan

   #include<iostream>  
   #include<string>  
   usingnamespacestd;  
      
   intmain()  
   {  
       string A,B;  
       cin >> A;  
       cin >> B;  
       intlenA = A.size();  
       intlenB = B.size();  
       intmaxLen=0;  
       for(inti=0;i<=lenB-lenA;i++)  
       {  
           intcurLen = 0;  
           for(intj=0;j<lenA;j++)  
           {  
               if(A[j]==B[i+j])  
                   curLen++;  
           }  
           if(curLen > maxLen)  
               maxLen = curLen;  
       }  
       cout << lenA-maxLen << endl;  
       return0;  
   }  

发表于 2018-07-27 17:29:21 回复(0)

牛客499848474号

测试用例abe，暗示安倍🤣

发表于 2024-10-07 16:25:29 回复(0)

Python3

lnu191491316

def difference(A, B): # 比较相同长度的字符串的差异

result = 0

length = len(A)

for i in range(length):

if A[i] != B[i]:

result += 1

return result

A = input()

B = input()

A_length = len(A)

B_length = len(B)

min_diff = A_length

diff = B_length - A_length # B只需要在头或尾共减少diff个字符即可

for front in range(diff + 1): # 0~diff

rear = diff - front # rear表示尾部减少的字符个数

temp = difference(A, B[front:B_length-rear+1:])

if min_diff > temp:

min_diff = temp

print(min_diff)

发表于 2024-05-03 09:38:37 回复(0)

牛客409434554号

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string a,b;cin>>a>>b;
    int len=a.length(),maxn=INT_MIN;
    for(int i=0;i<=b.length()-len;i++)
    {
        string t=b.substr(i,len);
        int sum=0;
        for(int j=0;j<len;j++)
            if(t[j]==a[j])    sum++;
        maxn=max(maxn,sum);
    }
    cout<<len-maxn;
}

发表于 2022-01-24 05:09:55 回复(0)

牛客438548264号

在A的左右都可以添加字符，不可插入，只要找到长度和A相等，差异最小的子串，他们的差异就是我们要的解

a=input()
b=input()
res=len(a)
for i in range(len(b)-len(a)+1):
temp=0
for x,y in zip(a,b[i:i+len(a)]):
if x!=y: temp+=1
res=min(res,temp)
print(res)

编辑于 2021-06-08 14:22:49 回复(0)

牛客329247131号

dfs模拟

最开始是模拟往a的开头或者结尾加上b里的任意一个字符，直到新的字符串长度等于b的长度。但是由于每次都要从set{b}里取一字符，时间复杂度太高。

改变思路，a加一个字符最匹配的字符等于b减一个字符，每次比较b减去首字母和尾字母的

不相等的字符数，取最小值即可。

A = input().strip()
B = input().strip()
dp = {}
def dfs(a, b):
    if len(a) == len(b):
        n = len(a)
        st = 0
        count = 0
        while st<n:
            if a[st] != b[st]:
                count += 1
            st += 1
        return count
    if dp.get(b):
        return dp[b]
    ans = float('inf')
    ans = min(ans, dfs(a, b[1:]), dfs(a, b[:-1]))
    dp[b] = ans
    return ans
print(dfs(A, B))

发表于 2021-04-13 18:02:42 回复(0)

啥玩意😭

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        char[] A = input.nextLine().toCharArray();
        char[] B = input.nextLine().toCharArray();
        int len = B.length - A.length;
        int res = Integer.MAX_VALUE;
       
        for(int i = 0;i<=len;i++){
            int count = 0;
            for(int j = 0;j<A.length;j++){
                if(A[j] !=B[j+i])
                    count++;

            }
            res = Math.min(res,count);
        }
        System.out.println(res);
    }
}

发表于 2019-04-25 16:34:42 回复(0)

大腿壮

最长公共子串问题，附带限制条件，子串不能超出主串的范围

def findLongestStr(s1, s2):

    # s1:主串
    # s2：匹配串
    dp = [[0] * (len(s2) + 1) for _ in range(len(s1) + 1)]
    max_value = 0
    for i in range(1, len(s1) + 1):
        for j in range(1, len(s2) + 1):
            if s1[i - 1] == s2[j - 1] and i >= j and i - j <= len(s1) - len(s2):
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = 0
            max_value = max(max_value, dp[i][j])
    return len(s2) - max_value

发表于 2019-03-15 20:13:57 回复(0)

乐观的摸摸头17

import sys

aStr = sys.stdin.readline().strip()
bStr = sys.stdin.readline().strip()
max = 0
for i in range(len(bStr)-len(aStr)+1):
    count = 0
    for j in range(len(aStr)):
        if(aStr[j] == bStr[i+j]):
            count += 1
    if(max < count):
        max = count
print (len(aStr)-max)

发表于 2018-09-05 01:18:34 回复(0)

G201806011649877

答案都这么写吗。。好吧是我想复杂了。。我以为题目中abc和abd这个例子还必须要顺序相同。。有没有跟我这么想得。。😂

发表于 2018-09-01 02:53:34 回复(1)

Tracy293

import java.util.Scanner;
public class Main{
public static void main(String args[]){
Scanner sc=new Scanner(System.in);
while(sc.hasNext()){
String m=sc.next();
String b=sc.next();
char[] mo=m.toCharArray();
char[] bye=b.toCharArray();
if(mo.length>bye.length)
continue;
int n=0;
int d=0;
for(int i=0;i<mo.length;i++){
for(int j= i;j<bye.length;j++){
if(mo[i]==bye[j]){
n++;
break;
}
}
}
d=mo.length-n;
System.out.println(d);
}
}
}

发表于 2018-08-31 23:57:47 回复(0)

Alex6666

   寻找A与B的字串最多相同字母
  
   #include<iostream>  
   #include<string>  
   using namespace std;  
   int main()  
   {  
       string A,B;  
       cin>>A>>B;  
       int la=A.length();  
       int lb=B.length();  
       intmax=0;  
       for(int i=0;i<lb-la+1;++i)  
       {  
           int count=0;  
           for(int j=0;j<la;++j)  
           {  
               if(A[j]==B[i+j])  
                   ++count;  
           }  
           if(max<count)  
               max=count;  
       }  
       cout<<la-max<<endl;  
       return 0;  
   }  

发表于 2018-07-31 11:24:48 回复(0)

WAK

  #include<bits/stdc++.h> 
  usingnamespacestd; 
  intmain(){ 
      string a,b; 
      while(cin>>a>>b){ 
          intdif = INT_MAX; 
          for(inti = 0;i<=b.size()-a.size();i++){ 
              intnum = 0; 
              for(intj = 0;j<a.size();j++){ 
                  if(a[j]!=b[j+i]) 
                      num++; 
              } 
              dif = dif<num?dif:num; 
          } 
          cout<<dif<<endl; 
      } 
      return0; 
  } 