【2022-08-27】美团秋招笔试前四道编程题

恭喜发现宝藏！搜索公众号【TechGuide】回复公司名，解锁更多新鲜好文和互联网大厂的笔经面经，目前已更新至美团、微软… 作者@TechGuide【全网同名】 点赞再看，养成习惯，您动动手指对原创作者意义非凡🤝

第一题：神奇字符 题目描述

小美在摆弄她的字符串。最近小团送了小美一个特殊字符 ’ * '，这个字符可以和其他所有字符匹配，除了这个字符外，其他字符只能自己和自己匹配。 小美先前有一个字符串S，长度为n，现在她又新组合了一个可有特殊字符 ’ * ’ 的字符串s，长度为m。

小美想知道有多少个位置 i，使得S[i+j]与s[j]对于1≤j≤m均能匹配上？

其中X[y]代表字符串X中第y位的字符。

输入描述

第一行两个空格隔开的正整数n和m，分别表示字符串S和字符串s的长度。 接下来一行长度为n的仅包含小写英文字母的字符串S 接下来一行长度为m的包含小写英文字母以及特殊字符 ’ * ’ 的字符串s 对于所有数据，1≤m≤n≤2000

输出描述

输出一行一个整数，表示满足要求的位置数量

代码 CPP版本

直接暴力

#include 

using namespace std;

int main(int argc, char* argv[]) {
    int n, m;
    cin >> n >> m;
    string a, b;
    cin >> a >> b;
    int ret = 0;
    for (int i = 0; i + m - 1 T[i - 1];
    }
    int ret = 0;
    vector id(m);
    iota(id.begin(), id.end(), 0);
    set sol;
    do {
        int ok = 1;
        for (int i = 0, j = 0; i  t[i];
    if (p[1] > M) {
        cout