E - Petya and Exam CodeForces - 832B 字典树+搜索

E - Petya and Exam

这个题目其实可以不用字典树写，但是因为之前写过poj的一个题目，意思和这个差不多，所以就用字典树写了一遍。

代码还是很好理解的，主要就是哪个findx函数，这个要好好理解。

如果碰到*或着？就要重新标记一下，其他都是一样的，对于？可以跳过好字母，对于*可以跳过若干个不好的字母，

这个就在直接跳过之前加一个判断条件就可以了。

贴一下代码

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<queue>

#include<algorithm>

#include<map>

#include<iomanip>

#define INF 99999999

using namespace std;

const int maxn = 1e5 + ;

typedef long long ll;

int tree[maxn][], tot = , ans, isgood[];

bool flag[maxn];

char good[], s[maxn], str[maxn];

int add(char *s) {

    int root = , id, len = strlen(s);

    for (int i = ; i < len; i++) {

        if (s[i] == '*') id = ;

        else if (s[i] == '?') id = ;

        else id = s[i] - 'a';

        if (!tree[root][id]) tree[root][id] = ++tot;

        root = tree[root][id];

        // printf("root=%d s=%c\n", root, s[i]);

    }

    flag[root] = true;

    return root;

}

void findx(char *s, int root, int pos) {

    // printf("%s root=%d pos=%d\n", s, root, pos);

    int len = strlen(s);

    if (pos > len) return;

    if (len == pos && flag[root]) {

        ans = ;

        return;

    }

    if (tree[root][]) {

        int flag = ;

        int len1 = strlen(str) - ;

        int ends = len1 - pos;

        // printf("ends=%d len-ends=%d pos=%d\n", ends, len - ends-1, pos);

        for (int i = pos; i <= len - ends - ; i++) {

            int id = s[i] - 'a';

            if (isgood[id]) {

                flag = ;

                break;

            }

        }

        // printf("flag=%d pos=%d len-ends=%d\n", flag, pos, len - ends);

        if (flag&&len - ends >= pos) findx(s, tree[root][], len - ends);

        // for (int j = pos; j <= len; j++) {

        //     int id = s[j] - 'a';

        //     if (isgood[id]) break;

        //     findx(s, tree[root][26], j + 1);

        // }

    }

    if (tree[root][]) {

        int length = strlen(good);

        for (int i = ; i < length; i++) {

            if (s[pos] == good[i]) findx(s, tree[root][], pos + );

        }

    }

    int id = s[pos] - 'a';

    if (s[pos] <= 'z'&&s[pos] >= 'a'&&tree[root][id]) findx(s, tree[root][id], pos + );

}

int main() {

    scanf("%s%s", good, str);

    int len = strlen(good);

    for (int i = ; i < len; i++) {

        int id = good[i] - 'a';

        isgood[id] = ;

    }

    int num = add(str);

    int m;

    scanf("%d", &m);

    while (m--) {

        scanf("%s", s);

        ans = ;

        findx(s, , );

        if (ans) printf("YES\n");

        else printf("NO\n");

    }

    return ;

}

字典树

Wild Words poj 1816

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<string>

#include<queue>

#include<algorithm>

#include<map>

#include<iomanip>

#define INF 99999999

using namespace std;

const int maxn = 2e6 + ;

typedef long long ll;

int tree[maxn][], tot = , ans, p[maxn];

bool flag[maxn], vis[maxn];

char s[maxn], str[maxn];

int add(char *s) {

    int root = , id, len = strlen(s);

    for (int i = ; i < len; i++) {

        if (s[i] == '*') id = ;

        else if (s[i] == '?') id = ;

        else id = s[i] - 'a';

        if (!tree[root][id]) tree[root][id] = ++tot;

        root = tree[root][id];

    }

    flag[root] = true;

    return root;

}

void findx(char *s, int root, int pos) {

    // printf("%s root=%d pos=%d\n", s, root, pos);

    int len = strlen(s);

    if (pos > len) return;

    if (len == pos && flag[root]) {

        vis[root] = ;

    }

    if (tree[root][]) {

        for (int i = pos; i <= len; i++) findx(s, tree[root][], i);

    }

    if (tree[root][])    findx(s, tree[root][], pos + );

    int id = s[pos] - 'a';

    if (s[pos] <= 'z'&&s[pos] >= 'a'&&tree[root][id]) findx(s, tree[root][id], pos + );

}

vector<int>res;

int main() {

    int n, m;

    scanf("%d%d", &n, &m);

    for(int i=;i<=n;i++)

    {

        scanf("%s", str);

        p[i]=add(str);

    }

    while(m--)

    {

        scanf("%s", str);

        findx(str, , );

        res.clear();

        for(int i=;i<=n;i++) if (vis[p[i]]) res.push_back(i - );

        int len = res.size();

        if (len == ) printf("Not match\n");

        else {

            for (int i = ; i < len - ; i++) printf("%d ", res[i]);

            printf("%d\n", res[len - ]);

        }

        for (int i = ; i <= n; i++) vis[p[i]] = ;

    }

    return ;

}

巴特西

E - Petya and Exam CodeForces - 832B 字典树+搜索

E - Petya and Exam

最新文章

热门文章