【Henu ACM Round #13 E】Spy Syndrome 2

在这里输入题意

【题解】

对m个串建立一棵字典树。然后对主串。尝试从第一个位置开始.在字典树中尝试匹配如果匹配到了位置i 就再从位置i+1开始尝试匹配 (这时又重新从根节点开始重新匹配每次匹配最多只要往下走50步。写个递归的过程就好。

【代码】

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6;
const int NN = 1e4;
const int M = 1e5;

int n,cnt,sta[NN+10];
int  tree[N+10][26],tot=1,val[N+10];
string S,s[M+10];

void _insert(int idx){
    int pos = 1;
    for (int i = (int)s[idx].size()-1;i>=0;i--){
        int key = tolower(s[idx][i])-'a';
        if (tree[pos][key]==0){
            tree[pos][key] = ++tot;
        }
        pos = tree[pos][key];
    }
    val[pos] = idx;
}

void out_ans(){
    for (int i = 1;i <= cnt;i++)
        cout <<s[sta[i]]<<' ';
    cout<<endl;
}

void dfs(int cur){
    if (cur==n-1){
        out_ans();
        exit(0);
    }
    int pos = 1;
    for (int i = cur+1;i<n ;i++){
        int key = S[i]-'a';
        if (tree[pos][key]!=0){
            pos = tree[pos][key];
        }else break;
        if (val[pos]!=0){
            cnt++;
            sta[cnt] = val[pos];
            dfs(i);
            cnt--;
        }
    }
}

int main(){
	#ifdef LOCAL_DEFINE
	    freopen("rush_in.txt", "r", stdin);
	#endif
	ios::sync_with_stdio(0),cin.tie(0);
    cin >>n;
    cin >> S;
    int num;
    cin >> num;
    for (int i = 1;i <= num;i++){
        cin >> s[i];
        _insert(i);
    }
    dfs(-1);
	return 0;
}

【Henu ACM Round #13 E】Spy Syndrome 2

相关推荐