英文分词

题目描述
众所周知，小葱同学擅长计算，尤其擅长计算组合数，但这个题和组合数没什么关系。
小葱同学自幼对语文非常感兴趣，而小葱同学从小也意识到中文与英文最大的一个区别便是分词。也正是因为中文存在分词的问题，才能诞生像“上海市长江大桥”这种脍炙人口的语句。为了将这种魅力带给英文语句，小葱现在把英文语句里面的空格全部删掉了，于是现在小葱想知道，给定一个英文语句和词表，有多少种对其分词的方案呢？
输入
第一行一个字符串代表英文句子。
第二行一个数N代表词表大小。
接下来N行每行一个字符串代表一个单词。
输出
输出若干行，每行一个分词方案。按照字典序从小至大输出，不同词之间用下划线进行连接。

样例输入
pineapplepenapple
5
apple
pen
applepen
pine
pineapple
样例输出
pine_apple_pen_apple
pine_applepen_apple
pineapple_pen_apple

题解：
枚举+dfs

代码：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1005;

string S;
string t[maxn];
string cnt[100005];
int num = 0;
int lens;
int n;

void dfs(string s, int len){
    if(len == lens){
        cnt[num ++] = s;
        return ;
    }

    for(int i = 1; i <= n; i ++){
        int v = t[i].size();
        if(len + v > lens)   continue;
        string w = S.substr(len, v);
        if(w == t[i]){
            string p;
            p = s + "_" + w;
            dfs(p, v + len);
        }
    }
}

int main()
{
    cin >> S;
    cin >> n;
    for(int i = 1; i <= n ;  i ++){
        cin >> t[i];
    }
    lens = S.size();
    for(int i = 1; i <= n; i ++){
            string p = t[i];
            if(S.substr(0, p.size()) == p)
                dfs(p, p.size());
    }

    sort(cnt, cnt + num);
    int m = unique(cnt, cnt + num) - cnt;
    for(int i = 0; i < m; i ++)
        cout << cnt[i] << endl;

    return 0;
}