백준 8789 (C++) Poezja z gwiazdką

최초 업로드: 2025-09-05 16:25:44

최근 수정 시간: 2025-09-06 14:32:57

게시자: rlatjwls3333

카테고리: 백준

# [Platinum IV] Poezja z gwiazdką

[문제 링크](https://www.acmicpc.net/problem/8789)

## 문제 설명

W pewnym egzotycznym języku indiańskim istnieje N różnych niepustych słów złożonych z małych liter alfabetu angielskiego.

Język posiada specyficzną właściwość, niespotykaną w żadnym innym języku. Otóż w piśmie używa się specjalnego znaku - gwiazdki ('*'), którym można zastąpić dowolny (być może pusty) spójny fragment pojedynczego słowa. Dzięku temu zapisane słowa stają się wieloznaczne, co sprawia, że w języku można pisać wyjątkowo głębokie wiersze. Utrudnia to codzienne życie, ale w końcu sztuka jest ważniejsza niż biografia.

Znając listę wszystkich słów w języku (w pełnym brzmieniu, bez gwiazdek) oraz tekst poematu, w którym w każdym słowie użyto dokładnie jednej gwiazdki, oblicz ile słów z języka odpowiada każdemu ze słów w poemacie.

Przykładowo, jeśli język zawiera słowa ["zupa","z","malpy","intruz","pyszny"], to w poemacie ["z*", "m*y", "g*ingo"] pierwszemu słowu poematu odpowiadają dwa słowa z języka, drugiemu - jedno, a trzeciemu - żadne (musiało dojść do błędu w druku).

## 입력

W pierwszej linii znajduje się liczba naturalna Z ( 1 <= Z <= 10 ) opisująca liczbę zestawów testowych. Następnie opisywane są kolejne zestawy.

W pierwszej linii opisu zestawu znajduje się liczba naturalna N ( 1 <= N <= 100000) oznaczająca liczbę słów w języku.

W kolejnych N liniach podawane są kolejne słowa z języka. Słowa są parami różne i każde składa się z minimalnie 1, a maksymalnie 10 małych liter alfabetu angielskiego.

W kolejnej linii opisu zestawu znajduje się liczba naturalna K ( 1 <= K <= 100000) oznaczająca liczbę słów w poemacie.

W kolejnych K liniach podawane są kolejne słowa poematu. Słowa nie muszą być parami różne, każde z nich składa się z minimalnie 1, a maksymalnie 10 znaków, z których dokładnie jeden to gwiazdka, a pozostałe są małymi znakami alfabetu angielskiego.

## 출력

Dla każdego zestawu należy w K liniach wypisać liczby słów z języka odpowiadających kolejnym słowom poematu.

## 풀이
모든 발생 가능 단어를 트라이에 넣고 개수를 세면 된다. 한번에 세면 메모리가 터져서 100개정도로 분할해서 구해주었다.

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

struct trie {
 vector<pair<char, trie*>> go;
 int finish=0;

~trie() {
        for(auto &e : go) delete e.second;
    }

void insert(const char* ch) {
        if(!*ch) {
            finish++;
            return;
        }

trie* next=0;
        for(auto g : go) {
            if(g.first==*ch) {
                next = g.second;
                break;
            }
        }
        if(!next) {
            go.push_back({*ch, new trie});
            next = go.back().second;
        }
        next->insert(ch+1);
    }

int find(const char *ch) {
        if(!*ch) return finish;

for(auto g : go) {
            if(g.first==*ch) {
                return g.second->find(ch+1);
            }
        }
        return 0;
    }
};

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 int n; cin >> n;
 vector<string> a(n);
 for(int i=0;i<n;i++) cin >> a[i];
 int k; cin >> k;
 vector<string> b(k);
 for(int i=0;i<k;i++) cin >> b[i];

vector<int> res(k);
 int len=n/100+1;
 for(int idx=0;idx<n;idx+=len) {
 trie *root = new trie;
 for(int i=idx;i<min(idx+len, n);i++) {
 string s = a[i];
 set<string> strings;
 for(int blankLen=0;blankLen<=s.length();blankLen++) {
 for(int blankIdx=0;blankIdx+blankLen<=s.length();blankIdx++) {
 string left = s.substr(0, blankIdx);
 string right = s.substr(blankIdx+blankLen, s.length()-(blankIdx+blankLen));
 strings.insert(left+"*");
 strings.insert("*"+right);
 strings.insert(left+"*"+right);
 }
 }
 for(string s : strings) root->insert(&s[0]);
 }
 for(int i=0;i<k;i++) res[i] += root->find(&b[i][0]);
 delete root;
 }
 for(int e : res) cout << e << '\n';
 }
}
```