문제
For each requested pattern, decide whether it appears as a contiguous substring anywhere in the shared text. Patterns may overlap and may repeat. Return results in the original query order. The limits require an approach that can handle many patterns efficiently.
Implement find_many_patterns(text, patterns).
Input
text: The text searched by every query.
patterns: The patterns, in query order.
Output
Return YES for each occurring pattern and NO for each absent one.
제약 조건
1…100,000 text characters. 1…100,000 nonempty patterns, with total length at most 500,000. All characters are lowercase a–z.
예시
입력:
text = "bananas"
patterns = ["ana", "apple", "nas"]
예상 출력:
expected = ["YES", "NO", "YES"]입력:
std::string text = "bananas";
std::vector<std::string> patterns = {"ana", "apple", "nas"};
예상 출력:
std::vector<std::string> expected = {"YES", "NO", "YES"};입력:
string text = "bananas";
string[] patterns = new string[] {"ana", "apple", "nas"};
예상 출력:
string[] expected = new string[] {"YES", "NO", "YES"};설명
Ana appears starting at position 2 and nas at position 5 (positions start at 1 here). Apple never appears.
입력:
text = "aaaa"
patterns = ["aa", "aaaaa", "aa"]
예상 출력:
expected = ["YES", "NO", "YES"]입력:
std::string text = "aaaa";
std::vector<std::string> patterns = {"aa", "aaaaa", "aa"};
예상 출력:
std::vector<std::string> expected = {"YES", "NO", "YES"};입력:
string text = "aaaa";
string[] patterns = new string[] {"aa", "aaaaa", "aa"};
예상 출력:
string[] expected = new string[] {"YES", "NO", "YES"};설명
Aa occurs despite overlapping matches. Five a characters cannot fit in a four-character text. The repeated aa query receives the same answer.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
여러 패턴이 작업을 공유할 수 있으니, 각 쿼리마다 텍스트를 따로 찾지 마세요.
힌트 2
패턴들을 한 구조에 모아 저장하고 텍스트를 한 번만 훑으면서, 문자가 들어올 때마다 매칭을 진행하세요.
힌트 3
중복 패턴은 쿼리 순서대로 보고해야 하고, 겹치는 매치는 각각 독립적으로 세어야 합니다.
예상 복잡도
시간 O(text length + total pattern length), 추가 공간 O(total pattern length)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.