思路:模拟

由于题目说只能改一次，所以我们可以很暴力的去解决这个问题：枚举改的这一次到底使用在哪？

我们要使用修改机会，只会在这两种情况下：

1.修改使得LCS更大

2.修改使得LCP更大

所以模拟这两种情况：

1.从左往右遇到第一个$s,t$ 不相等的位置，修改使其相等，求一下相似度。

2.从右往左遇到第一个$s,t$不相等的位置，修改使其相等，求一下相似度。

两者最大值即为答案。

代码

C++

#include <bits/stdc++.h>
using namespace std;
int getLcp (string a , string b){
    int n = a.size();
    int m = b.size();
	for (int i = 0 ; i < min(n , m) ; i++){
		if (a[i] != b[i]) return i;
	}
	return min(n , m);
}
int getLcs (string a , string b){
	string ra = a;
	string rb = b;
	reverse(ra.begin() , ra.end());
	reverse(rb.begin() , rb.end());
	return getLcp(ra , rb);
}
long long solve(string a , string b){
    int n = a.size();
    int m = b.size();
    char t;
    long long res1 = 1LL * getLcp(a , b) * getLcs(a , b); // 初始为最大可能取值
    long long res2 = res1;
	for (int i = 0 ; i < min(n , m) ; i++){ // 模拟情况1
		if (a[i] != b[i]) {
			t = a[i];
			a[i] = b[i];
			res1 = 1LL * getLcp(a , b) * getLcs(a , b); 
			a[i] = t;
			break;
		}
	}
	for (int i = 0 ; i < min(n , m) ; i++){ // 模拟情况2
		if (a[n - i - 1] != b[m - i - 1]) {
			t = a[n - i - 1];
			a[n - i - 1] = b[m - i - 1];
			res2 = 1LL * getLcp(a , b) * getLcs(a , b);
			a[n - i - 1] = t;
			break;
		}
	}
	return max(res1 , res2); // 返回
}
int main() {
    string a , b;
    cin >> a >> b;
    cout << solve(a , b) << endl;
    return 0;
}

Python

def get_lcp(a, b):
    n = len(a)
    m = len(b)
    for i in range(min(n, m)):
        if a[i] != b[i]:
            return i
    return min(n, m)

def get_lcs(a, b):
    ra = a[::-1]
    rb = b[::-1]
    return get_lcp(ra, rb)

def solve(a, b):
    n = len(a)
    m = len(b)
    res1 = get_lcp(a, b) * get_lcs(a, b) # Initial maximum possible value
    res2 = res1
    for i in range(min(n, m)): # Simulate case 1
        if a[i] != b[i]:
            t = list(a)
            g = t[i]
            t[i] = b[i]
            a = "".join(t)
            res1 = get_lcp(a, b) * get_lcs(a, b)
            t[i] = g
            a = "".join(t) # Restore a
            break
    for i in range(min(n, m)): # Simulate case 2
        if a[n - i - 1] != b[m - i - 1]:
            t = list(a)
            g = a[i]
            t[n - i - 1] = b[m - i - 1]
            a = "".join(t)
            res2 = get_lcp(a, b) * get_lcs(a, b)
            t[i] = g
            a = "".join(t) # Restore a
            break
    return max(res1, res2) # Return the maximum result

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

Java

import java.util.Scanner;

public class Main {
    public static int getLcp(String a, String b) {
        int n = a.length();
        int m = b.length();
        for (int i = 0; i < Math.min(n, m); i++) {
            if (a.charAt(i) != b.charAt(i)) {
                return i;
            }
        }
        return Math.min(n, m);
    }

    public static int getLcs(String a, String b) {
        StringBuilder ra = new StringBuilder(a).reverse();
        StringBuilder rb = new StringBuilder(b).reverse();
        return getLcp(ra.toString(), rb.toString());
    }

    public static long solve(String a, String b) {
        int n = a.length();
        int m = b.length();
        char[] arr = a.toCharArray();
        long res1 = (long) getLcp(a, b) * getLcs(a, b); // Initial maximum possible value
        long res2 = res1;
        for (int i = 0; i < Math.min(n, m); i++) { // Simulate case 1
            if (arr[i] != b.charAt(i)) {
                char t = arr[i];
                arr[i] = b.charAt(i);
                a = new String(arr);
                res1 = (long) getLcp(a, b) * getLcs(a, b);
                arr[i] = t; // Restore a
                break;
            }
        }
        for (int i = 0; i < Math.min(n, m); i++) { // Simulate case 2
            if (arr[n - i - 1] != b.charAt(m - i - 1)) {
                char t = arr[n - i - 1];
                arr[n - i - 1] = b.charAt(m - i - 1);
                a = new String(arr);
                res2 = (long) getLcp(a, b) * getLcs(a, b);
                arr[n - i - 1] = t; // Restore a
                break;
            }
        }
        return Math.max(res1, res2); // Return the maximum result
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String a = scanner.next();
        String b = scanner.next();
        System.out.println(solve(a, b));
    }
}