题解：AT_past202004_d パターンマッチ

yyycj · 2025-10-03 13:18:33 · 题解

题目简述

给你一个只包含小写字母的字符串 S。长度为 1 \sim 3 的字符串 T 与 S 匹配，需要满足只包括小写字母和 .，并且与 S 中的一个子串相同，. 可以代表任意字符，求与 S 匹配的 T 的个数。

主要思路

由于 T 的长度最多为 3，所以可以直接枚举 S 中长度为 1 \sim 3 的子串，然后枚举 T。T 中的字符要么是 .，要么是其对应的 S 中的字符，可以搜索或二进制枚举。但是可能会有重复字符串，需要用 set 去重。

AC Code

#include<set>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int INT_INF = 0x3f3f3f3f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
template<typename T1, typename T2, typename T3> T1 _pow(T1 a, T2 b, T3 mod = LL_INF) { T1 x = 1, y = a; while(b > 0) {if (b & 1) x = x * y % mod; y = y * y % mod; b >>= 1; } return x; }
// ----------------------------

// ----------------------------
set<string> st;
// ----------------------------
void dfs(int u, int n, string s, string t) {
    if (u >= n) {
        st.insert(t);
        return;
    }

    t += '.';
    dfs(u + 1, n, s, t);
    t.pop_back(); t += s[u];
    dfs(u + 1, n, s, t);
}

int main() {
    string s; cin >> s;
    // ----------------------------
    for (int i = 1; i <= 3; i++) {
        for (int j = 0; j + i - 1 < (int)s.length(); j++) {
            dfs(0, i, s.substr(j, i), "");
        }
    }
    // ----------------------------
    cout << st.size();
    return 0;
}