문제
패턴 문자열 P와 텍스트 문자열 T가 주어지면,
T에서 P가 (0-index 기반에서) 있는 모든 곳을 포함하는 배열을 반환하는FindAll<T, P>를 구현하라.
Given a pattern string P and a text string T, implement the type FindAll<T, P> that returns an Array that contains all indices (0-indexed) from T where P matches.
내 풀이
type FindAllImplement<T extends string,P extends string,Result extends number[]=[],Element extends any[]=[]>=
T extends `${infer _}${infer RestStr}`?
T extends `${P}${infer _}`?FindAllImplement<RestStr,P,[...Result,Element['length']],[...Element,0]>
:FindAllImplement<RestStr,P,Result,[...Element,0]>
:Result
type FindAll<T extends string, P extends string> =P extends ''?[]: FindAllImplement<T,P>
우선 사용처에서 구현용 제네릭을 사용하지 못하게 하기 위해 구현과 실제 타입을 분리했다.
그리고, P가 빈 문자열이면 항상 빈 배열을 반환하고, 빈 문자열이 infer과 만나면 문제가 생길 수 있으므로 사전에 처리해주었다.
FindAllImplement는 재귀적으로 구현되어있다.
실행흐름은 다음과 같다.
1) 만약 T가 빈 문자열이라면 Result를 반환한다.
2) 만약 T가 P로 시작한다면,Result에 현재 요소의 길이(Element['length'])를 넣어 다음 재귀로 넘어간다.
3) 만약 T가 P로 시작하지 않는면,Result를 그대로 넣어 다음 문자열로 넘어간다.
관련 개념
모든 문자열은 `${''}${string}` 를 확장 가능하다.
그러므로 FindAllImplement에서 P에 빈 문자열이 들어가게 되면 모든 문자열이 확장되게 된다.( 실행흐름 2) 참고)
