poj 1816 Trie + DFS 매 칭 모드 문자열

2792 단어 수색 하 다.데이터 구조문자열TrieDFS
Wild Words
Time Limit: 2000MS
 
Memory Limit: 65536K
Total Submissions: 4887
 
Accepted: 1274
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

일치 하 는 패턴 문자열 은 정규 표현 식 과 유사 합 니 다. 컴 파일 원 리 를 배 울 때 일치 하 는 문자열 을 기억 하고 상태 기 를 구축 해 야 합 니 다. 종이 에 그림 을 그 렸 을 때 AC 자동 동기 와 차이 가 많 지 않 지만 Trie 만 있 으 면 됩 니 다. Trie 로 상태 기 를 만 든 다음 DFS 로 일치 하면 됩 니 다. 특수 처리 해 야 할 것 은 * 의 일치 입 니 다. 비어 있 거나 여러 개 로 일치 할 수 있 습 니 다.몇 개의 구덩이 점 을 주의 하 십시오. 1. 패턴 문자열 은 중 복 될 수 있 습 니 다. 2. 오름차 순 으로 출력 -. - 3. 같은 문자열 이 같은 패턴 과 일치 하면 중 복 될 수 있 는 방법 (예 를 들 어 * a * a 와 aa) 이 있 습 니 다.
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define maxn 600010
struct Trie
{
    int next[maxn][28];
    vector end[maxn]; //end              ， vector             
    int tot,rt;
    int newnode()
    {
        memset(next[tot], -1, sizeof(next[tot]));
        end[tot++].clear();
        return tot-1;
    }
    void init()
    {
        tot=0;
        rt=newnode();
    }

    void insert(char *s, int tag)
    {
        int len=strlen(s);
        int cur=rt;
        for(int i=0; i
스 택 을 이용 하여 10 진 을 2 진 으로 변환 합 니 다.
TextView drawableRight in code

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage