LA 3942 트 리 + dfs (dp)

전송 문: LA 3942
제목
문자열 을 지정 합 니 다. s 단 어 를 주 고 문자열 이 이 단어 들 로 구 성 된 배열 수 (단 어 는 중복 가능) 를 구 합 니 다.
해제
dfs 와 유사 한 심층 검색 방안 수 구 해 는 구성 단위 가 단어 라 는 차이 가 있 기 때문에 trie 수로 단 어 를 저장 할 수 있 습 니 다. 검색 할 때 단어 검색 을 찾 을 수 있 습 니 다. 기억 화 검색 은 시간 소 모 를 줄 이 고 나 무 를 만 든 후에 dp 역순 으로 도 할 수 있 습 니 다. dfs 의 원리 와 같 습 니 다.
AC code
dfs 트 리 저장 은 노드 방식 입 니 다.

/*
adrui's submission
Language : C++
Result : Accepted
Love : yy
Favorite : Dragon Balls

Standing in the Hall of Fame
*/


#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define M(a, b) memset(a, b, sizeof(a))
#define mid ((l + r) >> 1)
#define ls rt << 1, l, mid
#define rs rt << 1|1, mid + 1, r
#define lowbit(x) (x & (-x))
#define LL long long
#define REP(n) for(int i = 0; i < n; i++)
#define debug 0

const int mod(20071027);
const int maxn(3e5 + 5);

int dp[maxn];

int idx(char p) {
    return p - 'a';
}


struct TrieTree {
    bool exist;
    TrieTree *next[26];

    TrieTree() {                                                
        M(next, 0);
        //cnt = 0;
        exist = false;
    }

    void insert_node(char *s) {                                 
        TrieTree *root = this;
        char *p = s;
        while (*p) {

            int tmp = idx(*p);

            if (root->next[tmp] == NULL) {
                root->next[tmp] = new TrieTree();
            }

            root = root->next[tmp];

            ++p;
        }

        root->exist = true;

    }

    int dfs(char *s, int tmp, int len) {

        if (tmp > len)  return 0;
        if (tmp == len) return 1;//       1
        if (dp[tmp] != -1)  return dp[tmp];
        dp[tmp] = 0;

        TrieTree *root = this;

        char *p = s;

        int cnt = 1;
        while (*p) {
            int temp = idx(*p);

            if (root->next[temp] == NULL) {//         
                break;
            }
            root = root->next[temp];
            if (root->exist) dp[tmp] += dfs(p + cnt, tmp + cnt, len);//      ，   
            ++cnt;
            ++p;
        }

        return dp[tmp] %= mod;
    }
};

int main() {
#if debug
    freopen("in.txt", "r", stdin);
#endif //debug

    cin.tie(0);
    cin.sync_with_stdio(false);


    char s[maxn];
    char word[105];



    int flag = 0, cnt, kase = 0;
    while (cin >> s) {
        TrieTree *root = new TrieTree();//   
        cout << "Case " << ++kase << ": ";
        cin >> cnt;
        while (cnt--) {
            cin >> word;
            root->insert_node(word);
        }

        M(dp, -1);
        int ans = root->dfs(s, 0, strlen(s));

        cout << ans << endl;
    }
    return 0;
}

역순 dp

/*
adrui's submission
Language : C++
Result : Accepted
Love : yy
Favorite : Dragon Balls

Standing in the Hall of Fame
*/


#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define M(a, b) memset(a, b, sizeof(a))
#define mid ((l + r) >> 1)
#define ls rt << 1, l, mid
#define rs rt << 1|1, mid + 1, r
#define lowbit(x) (x & (-x))
#define LL long long
#define REP(n) for(int i = 0; i < n; i++)
#define debug 0

const int mod(20071027);
const int maxn(5e5 + 5);

int dp[maxn];

int idx(char p) {
    return p - 'a';
}


struct TrieTree {
    bool exist;
    TrieTree *next[26];

    TrieTree() {                                                
        M(next, 0);
        //cnt = 0;
        exist = false;
    }

    void insert_node(char *s) {                                 
        TrieTree *root = this;
        char *p = s;
        while (*p) {

            int tmp = idx(*p);

            if (root->next[tmp] == NULL) {
                root->next[tmp] = new TrieTree();
            }

            root = root->next[tmp];

            ++p;
        }

        root->exist = true;

    }

    int Dp(char *s, int len) {

        dp[len] = 1;

        for (int i = len - 1; i >= 0; --i) {
            TrieTree *root = this;//   
            for (int j = i; j < len; ++j) {
                int temp = idx(s[j]);
                //cout << s[j] << endl;
                if (root->next[temp] == NULL) {// dfs    
                    break;
                }
                root = root->next[temp];
                if (root->exist == true) {
                    dp[i] = (dp[i] + dp[j + 1]) % mod;//     
                    //cout << j + 1 << " " << len << endl;
                }
            }
            dp[i] %= mod;
        }

        return dp[0];
    }
};

int main() {
#if debug
    freopen("in.txt", "r", stdin);
#endif //debug

    cin.tie(0);
    cin.sync_with_stdio(false);


    char s[maxn];
    char word[105];



    int flag = 0, cnt, kase = 0;
    while (cin >> s) {

        TrieTree *root = new TrieTree();
        cout << "Case " << ++kase << ": ";
        cin >> cnt;
        while (cnt--) {
            cin >> word;
            root->insert_node(word);
        }

        M(dp, 0);
        int ans = root->Dp(s,strlen(s));

        cout << ans << endl;
    }
    return 0;
}

총결산
이 문 제 는 오후 에 30 분 동안 생각 하고 싶 습 니 다. 첫 번 째 코드 10 분, debug 1 시간.