O (n) 시간 대괄호 패턴이있는 O (1) 부분 문자열 검색

Question

O (n) 런타임 및 O (1) 작업 공간이있는 정확히 두 개의 알려진 알고리즘이 있습니다. SMOA 및 양방향 http://www-igm.univ-mlv.fr/~lecroq/string/ 참조). 둘 다 알파벳을 주문하거나 부과하는 것에 의존합니다.

고정 부분 문자열을 검색하는 대신 브래킷 표현식으로 표현 된 부분 문자열 집합 중 하나를 검색 할 수 있기를 원합니다.

[abc]d 

은 "ad", "bd"또는 "cd"와 일치합니다. 알파벳이 유한하다고 가정하면, 괄호의 길이는 한정되어 있으므로, 시간이나 공간 요구 사항에서 "괄호 길이"형식의 용어는 모두 O (1)입니다.

O (n) 시간 (여기서 n은 검색 할 문자열의 길이, 즉 "건초 더미") 및 O (1) 작업 공간에서 검색을 수행 할 수 있습니까?

해결 방법에 알파벳 순서가있는 대괄호 세트를 사용하는 경우가 아니면이 문제에 대한 해결책은 주문 요구 사항없이 O (n)/O (1)의 고정 하위 문자열 검색 문제에 대한 새로운 해결책을 제공하고 따라서 존재할 것 같지 않다.

Answer 1

나는 뭔가를 놓치고 있어야합니다. 링크 된 페이지에서 무차별 방식은 O (n)입니다.

1. Pattern is P with index p indicating which element of the pattern we are on. 
2. String is S with index s indicating which element of the string we are on. 
3. if S[s] matches P[p], increment both indicies and repeat until you complete the Pattern. 
4. If S[s] doesn't match P[p], set p=0 and increment p. 

이는 O (n)이고 사용자의 요구 사항을 충족시킬 것입니다.