笔试时间：2023年8月27日 秋招

第一题

题目：小红的字符串相似度

假设字符串s和t的最长相同前缀的长度是a，最长相同后缀的长度是6。小红认为字符串s和t的相似度是a x b。现在小红想进行最多一次修改，s的一个小写字母改成另一个小写字母，使得相似度尽量大。问相似度最大是多少？

输入描述

第一行输入一个仅包含小写字母的字符串s；

第二行输入一个仅包含小写字母的字符串t；

1 < len(s), len(t) < 10^5

输出描述

输出一个整数。

样例输入

abc

abba

样例输出

4

提示：

将s串的第三个字符改成‘a’，s串变成"aba"。最长相同前经和后缀分别是"ab"和"ba”。

参考题解

Python：

def cal(s, t):
    p = 0
    q = 0
    n = len(s)
    m = len(t)

    while p < n and p < m and s[p] == t[p]:
        p += 1

    while n - q > 0 and m - q > 0 and s[n - q - 1] == t[m - q - 1]:
        q += 1

    return p * q


def main():
    s = input()
    t = input()
    n = len(s)
    m = len(t)

    ans = cal(s, t)

    p = 0
    q = 0

    while p < n and p < m and s[p] == t[p]:
        p += 1

    if p < n and p < m:
        ch = s[p]
        s = s[:p] + t[p] + s[p + 1:]
        ans = max(ans, cal(s, t))
        s = s[:p] + ch + s[p + 1:]

    while n - q > 0 and m - q > 0 and s[n - q - 1] == t[m - q - 1]:
        q += 1

    if n - q > 0 and m - q > 0:
        ch = s[n - q - 1]
        s = s[:n - q - 1] + t[m - q - 1] + s[n - q:]
        ans = max(ans, cal(s, t))
        s = s[:n - q - 1] + ch + s[n - q:]

    print(ans)


if __name__ == "__main__":
    main()

第二题

题目：小红的颜色矩阵

小红拿到了一个短阵，矩阵中格子的颜色为红色、绿色或者蓝色。现在小红有q次询问，每次询问一个子矩阵，希望你输出这个子短阵的颜色种类数。

输入描述

第一行输入两个正整数n,m，代表矩阵的行数和列数；

接下来的n行，每行输入m个字符串(字符串一定是“red"”、"green"、"blue"中的一种，代表格子的颜色)；

接下来的一行，输入一个正整数q，代表小红的询问次数；

接下来的q行，每行输入四个正整数x1,y1,x2,y2代表询问的子矩阵左上角为第x1行第y1列，右下角为第x2行第y2列。

输出描述

输出q行，每行输出一个整数，代表颜色的数量。

样例输入

3 3

red blue blue

red blue blue

green green green

2

1 2 2 3

2 1 3