题解：AT_past202004_d パターンマッチ

chenyuan3 · 2025-09-30 22:47:34 · 题解

枚举每一个可能的 t，判断是否合法。枚举的方法有很多：

• 可以用深度优先搜索，代码中使用了先序遍历的方式，深搜时搜到的当前字符串只要非空就判断，然后再继续枚举。
• 此外还可以用广度优先搜索等方式，这里不过多赘述。

:::info[代码]

提交记录。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ans;
string s, t;
void dfs()
{
    if (t.size() > 3)
    {
        return;
    }
    if (t.size())
    {
        for (ll i = 0; i <= (ll)s.size() - (ll)t.size(); i++)
        // string/vector 等 STL 容器的 .size() 方法的返回值是无符号整数，代码中可能会遇到 s 比 t 长的情况，此时减出来负数会溢出变成一个很大的数导致错误。
        {
            bool flag = true;
            for (ll j = 0; j < t.size(); j++)
            {
                if (s[i + j] != t[j] && t[j] != '.')
                {
                    flag = false;
                    break;
                }
            }
            if (flag)
            {
                ans++;
                break;
            }
        }
    }
    for (char i = 'a'; i <= 'z'; i++)
    {
        t += i;
        dfs();
        t.pop_back();
    }
    t += '.';
    dfs();
    t.pop_back();
}
void solve()
{
    cin >> s;
    dfs();
    cout << ans;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}

:::