백준 9250 (C++) 문자열 집합 판별

최초 업로드: 2025-04-21 20:40:36

최근 수정 시간: 2025-07-25 09:24:42

게시자: rlatjwls3333

카테고리: 백준

# [Platinum II] 문자열 집합 판별

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

## 문제 설명

집합 S는 크기가 N이고, 원소가 문자열인 집합이다. Q개의 문자열이 주어졌을 때, 각 문자열의 부분 문자열이 집합 S에 있는지 판별하는 프로그램을 작성하시오. 문자열의 여러 부분 문자열 중 하나라도 집합 S에 있으면 'YES'를 출력하고, 아무것도 없으면 'NO'를 출력한다.

예를 들어, 집합 S = {"www","woo","jun"} 일 때, "myungwoo"의 부분 문자열인 "woo" 가 집합 S에 있으므로 답은 'YES'이고, "hongjun"의 부분 문자열 "jun"이 집합 S에 있으므로 답은 'YES'이다. 하지만, "dooho"는 모든 부분 문자열이 집합 S에 없기 때문에 답은 'NO'이다.

## 입력

첫째 줄에 집합 S의 크기 N이 주어진다. (1 ≤ N ≤ 1000)

다음 N개 줄에 집합 S의 원소들이 주어진다. 이 문자열의 길이는 100을 넘지 않는다.

다음 줄에 답을 판별해야 하는 문자열의 개수 Q가 주어진다. (1 ≤ Q ≤ 1000)

다음 Q개 줄에 답을 판별해야 하는 문자열이 주어진다. 이 문자열의 길이는 10000을 넘지 않는다.

입력으로 주어지는 모든 문자열은 알파벳 소문자로만 이루어져 있다.

## 출력

Q개 줄에 각 문자열에 대한 답을 출력한다.

## 풀이
#### 아호코라식 알고리즘을 써서 각 단어의 글자를 순서대로 살펴보다 finish일 때 종료하면 된다.

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

struct trie {
    trie* go[26] = {0, };
    bool finish=false;
    trie* fail;

void insert(char* ch) {
        if(*ch==NULL) {
            finish=true;
            return;
        }

if(!go[*ch-'a']) go[*ch-'a'] = new trie;
        go[*ch-'a']->insert(ch+1);
    }
};

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int n; cin >> n;
    trie* root = new trie;

while(n--) {
        string s; cin >> s;
        root->insert(&s[0]);
    }

queue<trie*> q; q.push(root);
 root->fail = root;
 while(!q.empty()) {
 trie* cur = q.front(); q.pop();
 for(int i=0;i<26;i++) {
 if(!cur->go[i]) continue;
 trie* next = cur->go[i];

if(cur==root) {
                next->fail = root;
            } else {
                trie* dest = cur->fail;
                while(dest!=root && !dest->go[i]) dest = dest->fail;
                if(dest->go[i]) dest = dest->go[i];
                next->fail = dest;
            }
            if(next->fail->finish) next->finish=true;
            q.push(next);
        }
    }

int Q; cin >> Q;
 while(Q--) {
 string s; cin >> s;
 trie* cur = root;
 for(int i=0;i<s.length();i++) {
 while(cur!=root && !cur->go[s[i]-'a']) cur = cur->fail;
 if(cur->go[s[i]-'a']) cur = cur->go[s[i]-'a'];
 if(cur->finish) break;
 }
 if(cur->finish) cout << "YES\n";
 else cout << "NO\n";
 }
}
```