SRM 689 div2 medium NonDeterministicSubstring

問題

問題概要

文字列AとBが与えられる。Bの文字の中には?が含まれていて、それを1または0に変換したものが、文字列Cとなる。文字列Aの連続部分列と文字列Bが一致いしている文字列Cの数を求める。(重複しているものは数えない)

解法

一番初めに思いついた解答は、Bの?を0または1に変換した文字を作り、それが文字列Aに存在するかを探す解法。これは、最高?が50個になるので、Bを変換する部分のみで、O(2⁵⁰)となり、TLEしていしまう。
ほかの見方をしてみると、この問題は、単にAのBの長さの連続部分列の種類の数を求めているようなもの。ただし、そのAの部分列は、Bの?以外の文字は一致いしていなければならない。?はBのほうで自由に変えられるため。後は、その連続部分列をsetにいれて重複をなくし数を求めればいい。

ミス

返り値がlong long 指定になっているので、数がとても多い気がして、setにinsertしたら、間に合わないよなーとかだいぶ悩んだけど、答えの数は全然大きくならない。

コード

#include <iostream>
#include <string>
#include <vector>
#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

//long long だからめっちゃ多い気がしてだまされたよね
class NonDeterministicSubstring{
public:
    long long ways(string A, string B){
        set<string> ans;
        if(A.size() < B.size()) return 0;
        for (int i = 0; i < A.size(); ++i){
            if(i + B.size() > A.size()) break;
            for (int j = 0; j < B.size(); ++j){
                if(A[i + j] != B[j] && B[j] != '?') break;
                if(j == B.size() - 1) ans.insert(A.substr(i, B.size()));
            }
        }
        return ans.size();
    }   
};