SPOJ Hacking（字典树 + 搜索）题解

思路1:字典树存每个串，然后dfs遍历是否存在。这里有个技巧，如果每次都重新初始化字典树为-1，那么会超时，所以我先初始化为-1，然后设一个Case，每个test时Case都++，那么只要开一个数组判断是否等于Case，如果等于就说明有这条路，不等则没有。这道题用字典树做要注意剪枝。

思路2：这道题能随机看命过

代码1:

#include<queue>

#include<cstring>

#include<set>

#include<map>

#include<stack>

#include<cmath>

#include<vector>

#include<cstdio>

#include<iostream>

#include<algorithm>

typedef long long ll;

const int maxn = 1e4 + ;

const int seed = ;

const ll MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

using namespace std;

int n, m, k, length, Case;

char s[maxn], ans[];

int trie[maxn * ][], cs[maxn * ][], tot;

void update(int st){

    int p = ;

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

        if(st + i > n) return;

        int v = s[st + i] - 'a';

        if(v >= k) return;    //剪枝

        if(cs[p][v] != Case){

            trie[p][v] = ++tot;

            cs[p][v] = Case;

        }

        p = trie[p][v];

    }

}

bool dfs(int p, int len){

    if(len > m) return false;

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

        if(cs[p][i] != Case){

            ans[length++] = 'a' + i;

            return true;

        }

        else if(dfs(trie[p][i], len + )){

            ans[length++] = 'a' + i;

            return true;

        }

    }

    return false;

}

int main(){

    int t;

    Case = ;

    memset(cs, -, sizeof(cs));

    scanf("%d", &t);

    while(t--){

        Case++;

        tot = ;

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

        scanf("%s", s + );

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

            update(i);

        }

        length = ;

        dfs(, );

        for(int i = length - ; i >= ; i--)

            printf("%c", ans[i]);

        printf("\n");

    }

    return ;

}

代码2：

#include<queue>

#include<cstring>

#include<set>

#include<map>

#include<stack>

#include<string>

#include<cmath>

#include<vector>

#include<cstdio>

#include<iostream>

#include<algorithm>

typedef long long ll;

const int maxn = 1e4 + ;

const int seed = ;

const ll MOD = 1e9 + ;

const int INF = 0x3f3f3f3f;

using namespace std;

int n, m, k;

char s[maxn];

int main(){

    int t;

    srand(time(NULL));

    scanf("%d", &t);

    while(t--){

        map<string, int> st;

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

        scanf("%s", s + );

        for(int i = ; i <= n - m + ; i++){

            string ss;

            for(int j = i; j < i + m; j++){

                ss += s[j];

            }

            st[ss] = ;

        }

        string ans;

        while(true){

            ans = "";

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

                ans += 'a' + rand() % k;

            }

            if(st[ans] == ){

                cout << ans << endl;

                break;

            }

        }

    }

    return ;

}

巴特西

SPOJ Hacking（字典树 + 搜索）题解

最新文章

热门文章