Article From:https://www.cnblogs.com/dilthey/p/9973362.html

Topic link:

http://poj.org/problem?id=1816

http://bailian.openjudge.cn/practice/1816?lang=en_US

Time Limit: 2000MS  Memory Limit: 65536K

Description

A word is a string of lowercases. A word pattern is a string of lowercases, ‘?’s and ‘*’s. In a pattern, a ‘?’ matches any single lowercase, and a ‘*’ matches none or more lowercases.

There are many word patterns and some words in your hand. For each word, your task is to tell which patterns match it.

Input

The first line of input contains two integers N (0 < N <= 100000) and M (0 < M <=100), representing the number of word patterns and the number of words. Each of the following N lines contains a word pattern, assuming all the patterns are numbered from 0 to N-1. After those, each of the last M lines contains a word.

You can assume that the length of patterns will not exceed 6, and the length of words will not exceed 20.

Output

For each word, print a line contains the numbers of matched patterns by increasing order. Each number is followed by a single blank. If there is no pattern that can match the word, print “Not match”.

Sample Input

5 4
t*
?h*s
??e*
*s
?*e
this
the
an
is

Sample Output

0 1 3
0 2 4
Not match
3

 

Title:

Give $n $pattern strings (containing only lowercase letters, “?” and “*”), $m $string (containing only lowercase letters),

In the pattern string “?” means that any letter can be matched, and “*” means that any number of letters can be matched (which can be $0).

Now for the $m $string, the query number is $0sim n-1 $How many of the $n $pattern strings are matchable?

 

Explanation:

A dictionary tree is established for $n $pattern strings, and DFS matching for $m $string queries is performed on the dictionary tree for each string.

Put several sets of data:

3 1
t
t*
t**
t
1 1
*j*j
jjj
2 1
abc
abc
abc

 

ACCode:

#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int maxn=100000+5;
int n,m;

namespace Trie
{
    const int SIZE=maxn;
    int sz;
    struct TrieNode{
        vector<int> pos;
        int nxt[28];
    }trie[SIZE];
    void init(){sz=1;}
    int idx(const char& c)
    {
        if(c=='?') return 26;
        if(c=='*') return 27;
        return c-'a';
    }
    void insert(const string& s,int id)
    {
        int p=1;
        for(int i=0;i<s.size();i++)
        {
            int ch=idx(s[i]);
            if(!trie[p].nxt[ch]) trie[p].nxt[ch]=++sz;
            p=trie[p].nxt[ch];
        }
        trie[p].pos.push_back(id);
    }

    void dfs(vector<int>& ans,int p,const string& s,int k)
    {
        if(trie[p].nxt[27]) {
            for(int i=0;k+i<=s.size();i++) dfs(ans,trie[p].nxt[27],s,k+i);
        }
        if(k>=s.size())
        {
            for(int i=0;i<trie[p].pos.size();i++) ans.push_back(trie[p].pos[i]);
            return;
        }
        int ch=idx(s[k]);
        if(trie[p].nxt[26]) dfs(ans,trie[p].nxt[26],s,k+1);
        if(trie[p].nxt[ch]) dfs(ans,trie[p].nxt[ch],s,k+1);
    }
};

int main()
{
    scanf("%d%d",&n,&m);
    Trie::init();
    char s[23];
    for(int i=0;i<n;i++)
    {
        scanf("%s",&s);
        Trie::insert(s,i);
    }

    vector<int> ans;
    for(int i=1;i<=m;i++)
    {
        scanf("%s",&s);
        ans.clear();
        Trie::dfs(ans,1,s,0);
        if(ans.empty()) printf("Not match\n");
        else
        {
            sort(ans.begin(),ans.end());
            ans.erase(unique(ans.begin(),ans.end()),ans.end());
            for(int k=0;k<ans.size();k++) {
                printf("%d%c",ans[k],(k==ans.size()-1)?'\n':' ');
            }
        }
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *