题解：AT_past202004_d パターンマッチ

MarkLikeFlorr · 2025-10-05 10:27:25 · 题解

思路：

可以看出，题目中要求的字符串必定是原字符串的子串将任意个字符替换成点构成的，所以我们可以枚举原字符串的子串并递推枚举替换点的情况。

代码：

#include <bits/stdc++.h>
using namespace std;

string s;
set<string> c;
int cnt=0;

void add(string x,int n){
    int l=x.size();
    if(n==l){
        c.insert(x);
        return;
    }
    add(x,n+1);
    x[n]='.';
    add(x,n+1);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>s;
    int n=s.size();
    for(int k=1;k<=3;k++){
        for(int i=0;i<=n-k;i++){
            c.insert(s.substr(i,k));
        }
    }

    for(auto i:c){
        add(i,0);
    }

    cout<<c.size();

    return 0;
}

附Atcoder AC记录