专栏文章

题解:AT_past202004_d パターンマッチ

AT_past202004_d题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@minqr1yt
此快照首次捕获于
2025/12/02 06:49
3 个月前
此快照最后确认于
2025/12/02 06:49
3 个月前
查看原文
枚举每一个可能的 tt,判断是否合法。枚举的方法有很多:
  • 可以用深度优先搜索,代码中使用了先序遍历的方式,深搜时搜到的当前字符串只要非空就判断,然后再继续枚举。
  • 此外还可以用广度优先搜索等方式,这里不过多赘述。
代码CPP
#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;
}

评论

2 条评论,欢迎与作者交流。

正在加载评论...