2016 UESTC Training for Search Algorithm & String H – 中二少女与字符串 Trie 字典树

  Source

2016 UESTC Training for Search Algorithm & String

  My Solution

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
using namespace std;
 
//CHARSE 为字符集大小
//BASE 为字符集ASCII 最小字符
//MAX_NODE 为最大点数
const int CHARSE = 26, BASE = 'a', MAX_NODE = 1e7 + 8;          //!!!!!!前面MAX_NODE开的太小， WA1 怎么不RE呢
//!!!!!!                           确实是这里  看样子当不能确定MAX_NODE多大的时候还是在不超内存的情况下尽可能大好了
//struct Trie{
    int tot, root, child[MAX_NODE][CHARSE];
    //bool flag[MAX_NODE];
    inline void Trie()
    {
        memset(child[1], 0, sizeof child[1]);
        //flag[1] = false;
        root = tot = 1;
    }
/*
    void _insert(const char* str)
    {
        int *cur = &root;
        for(const char *p = str; *p; p++){
            cur = &child[*cur][*p - BASE];
            if(*cur == 0){
                *cur = ++tot;
                memset(child[tot], 0, sizeof child[tot]);
                flag[tot] = false;
            }
        }
        flag[*cur] = true;
    }
*/
    inline void _insert(const char* str, const int& n)
    {
        int *cur = &root;
        const char *endptr = str + n;                 //
        for(const char *p = str; p != endptr; p++){
            cur = &child[*cur][*p - BASE];
            if(*cur == 0){
                *cur = ++tot;
                memset(child[tot], 0, sizeof child[tot]);
                //flag[tot] = false;
            }
        }
        //flag[*cur] = true;
    }
/*
    bool query(const char *str)
    {
        int *cur = &root;
        for(const char *p = str; *p && *cur; p++)
            cur = &child[*cur][*p - BASE];
        return (*cur && flag[*cur]);
    }
    bool query(const char *str, const int& n)
    {
        int *cur = &root;
        const char* endptr = str + n;
        for(const char *p = str; p != endptr && *cur; p++)   //这个是根据上面改成插入 str[i,....i+n] 这一段， 可能有错误
            cur = &child[*cur][*p - BASE];
        return (*cur && flag[*cur]);
    }
*/
//};
 
const int maxn = 1500 + 8;
map<char, bool> _map;
 
char line[maxn], or01[27];
 
int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    #endif // LOCAL
    int T, n, k, cnt;
    scanf("%d", &T);
    while(T--){
        Trie();
        //_map.clear(); //not necessary
        scanf("%s", line);
        scanf("%s", or01);
        scanf("%d", &k);
 
        for(int i = 0; i < 26; i++){
            _map[i + 'a'] = or01[i] - '0';
        }
        n = strlen(line);
        cnt = 0;
 
        for(int i = n-1, j = n-1; i >= 0; i--){
            if(!_map[line[i]]) cnt++;
            while(cnt > k){
                if(!_map[line[j--]]) cnt--;
            }
            //cout<<"here"<<endl;
            //从左到右要加上这个for(int l = j; l <= i; l++)    //!前面这里用了 k = j
                _insert(line + i, j - i + 1);  //line + j, 不是 line + i 拜托
        }
        printf("%d\n", tot - 1);  //边数 == 借的书 - 1 即为Trie中子串总数
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx