ps:문자열
문자열
- 문자열 관련해서 PS레벨에서 알아야 할 알고리즘들은 어느정도 정해져있는 편이고, 그다지 많지 않다.
- 어려운 점은 어떤 문제에 어떤 알고리즘을 어떻게 적용해야 할지이다.
- 처음에 kmp와 z알고리즘을 공부하고서 관련 문제를 풀어보는데 언제 뭘써야 하고, 뭐가 되고 뭐가 안되고가 엄청 헷갈렸다, 어찌어찌 답은 나오더라도 과정이 머릿속에 명확하지 못하고.. 풀이를 보더라도 다른 문제에 확장이 잘 안됐다.
- 이게 풀이에서는 'kmp를 이렇게 이렇게 쓰면 이 문제를 풀수 있다' 주로 이런식으로만 적혀있는데.. 내가 고심한 결과 다른 문제에 적용하는 능력을 기르려면, 알고리즘에서 문제로 바로 연결되는게 아니라, 중간 단계 태스크를 추가해서 정리해야할 필요가 있다는 것을 알았다. 즉 'KMP를 쓰면 이런 것을 할수있다. 이런것을 할수 있으면 이 문제를 풀수있다' 이런식으로 정리를 해보려고 했고.. 이러면, '이런것은, z 알고리즘을 써도 할수 있다. 따라서 이 문제는 z 알고리즘으로도 풀수 있다' 이렇게 문제를 명확하게 이해하는데 큰 도움이 되었다.
- 그래서 나름대로 정리한 내용들을 모아보기는 하는데.. 이게 다른곳에서 이렇게 정리된것을 가져온게 아니라 내가 이해한것들을 독자적으로 정리한 내용에 가까워서 추후 언제든 수정될수 있다..
러프하게 분류한 접근 방법들
- 여러개의 문자열들을 갖고 뭔가를 한다
- 일단 문자열들을 트라이로 관리해보자
- 트라이는 여러개의 문자열들을 가장 효율적으로 관리할수 있는 구조이다.
- 문자열 셋 중에서, 특정 문자열이 있는지, 특정 prefix로 시작하는 문자열이 있는지, prefix가 가장 길게 겹치는 문자열이 뭔지 등등을 효율적으로 찾을수 있다
- 문제에 따라서는 그냥 소팅만 해놓고 거기에서 찾아서 써도 풀리는 문제도 있긴 하다.
- 주어진 문자열의 prefix에 관한 문제
- 주어진 문자열이 prefix에 관련된 조건을 만족하는지, 조건을 만족하는 prefix가 몇개인지, 조건을 만족하는 prefix중 가장 긴것이 뭐인지 등등.
- fail함수와 z배열은 할수 있는 일이 거의 비슷하다. 둘다 prefix와 일치하는 부분문자열의 정보를 갖는다. fail[i]은 i위치에서 끝나면서 prefix와 일치하는 가장 긴 부분문자열의 길이를, z[i]는 i위치에서 시작하면서 prefix와 일치하는 가장 긴 부분문자열의 길이를 저장한다. 대충 편한걸로 쓰면 된다.
- 'prefix이면서 suffix인 부분문자열이…' 이런 문제가 나오면 kmp나 z로 풀수 있을 확률이 좀더 올라간다
- 문자열의 반복패턴에 관한 문제도 이것으로 풀수 있다.
- 주어진 문자열의 부분문자열에 관한 문제
- prefix가 아니라 좀더 일반적인 '부분문자열'에 관한 문제가 나온다면 접미사 배열 (Suffix Array)를 써야 할 가능성이 크다.
- SA로 푸는 대표적인 문제는 서로다른 부분문자열의 갯수, 두번 이상 등장하는 가장 긴 부분문자열, 어떤 두 부분문자열의 최장접두사 찾기 등이다.
- 이 외에도 활용여부가 무궁무진한것 같긴 하지만.. 아직 많이 접해보지는 않았다
- 그 외에 좀더 특수한 유형에 적용되는 알고리즘들
- 문자열 매칭이라면 kmp를 쓰자
- '팰린드롬'에 관련된 문제라면 매내처 알고리즘을 생각해보자
- 'repetition'에 관련된 문제라면 Main-Lorentz 알고리즘을 써야 할수도 있다.
- 'wildcard를 포함하는 문자열 매칭' 에 관련된 문제라면 FFT를 써야할수도 있다.
Prefix 관련 태스크
각각의 prefix의 등장 횟수를 모두 세기
- z배열 이용
- 가장 직관적이다. z[i]가 l이라면, i부터 시작하는 1,2,3,..,l 길이의 문자열이 모두 prefix이라는 말이고, 그러니까 길이 1짜리 prefix, 길이 2짜리 prefix, .., 길이 l짜리 prefix들의 등장횟수를 모두 1 증가시켜주면 된다. 누적합을 이용하면 간단.
counter = collections.Counter(z) for i in reversed(range(len(S))): counter[i] += counter[i + 1]
- fail 함수 이용
- 덜 직관적이긴 하지만, 가능하다. z배열과 달리, i에서 끝나는 l길이의 문자열이 prefix라고 해서, i에서 끝나는 l-1,l-2,..1 길이의 문자열도 prefix가 되는것은 아니다, 하지만, fail[i-1], fail[fail[i-1]],… 이 prefix가 된다는 것은 알고 있다. 이것을 이용해서 로직을 조금 더 정리하면 아래처럼 할 수 있다.
fail = tstring.failure_table(S) counter = collections.Counter(fail) for i in range(len(S) - 1, 0, -1): counter[fail[i - 1]] += counter[i] counter[i] += 1 counter[len(S)] = 1
- 관련 문제: Prefix와 Suffix
Border 관련 태스크
- Border 는 어떤 문자열의 prefix이면서 동시에 suffix인 부분문자열을 말한다.
- Border를 이용해서 처리되는 문자열 관련 문제들이 많다.
기본 테크닉
- 가장 긴 proper Border(의 길이) 찾기
- fail 펑션이 있다면 : fail[-1]
- Z array가 있다면 :
- Border를 모두 찾기
- s[:l] == s[-l:] 인 l을 모두 찾는다
- fail 펑션 이용
fail = tstring.failure_table(S) l = len(S) border_lens = [len(S)] while l := fail[l - 1]: border_lens.append(l)- (내림차순으로 저장됨)
- Z 배열 이용
z = tstring.z_array(S) border_lens = [i for i, z_i in enumerate(reversed(z), start=1) if i == z_i]- (오름차순으로 저장됨)
반복 찾기
- 반복..은 내가 적당히 붙인 말이라서 좀 추상적이니까 좀더 정확히 정의해보자. 문자열을 부분문자열의 반복으로 표현하는 것을 생각하자.
- S=abcdabcdabcdabc 와 같은 문자열을 반복으로 표현하면..
- 'abcd'가 반복문자열이라고 해석할수 있다. T='abcd'=S[:4]라고 두면 S=S[:4]*3+S[:3]으로 표현할수 있다.
- 'abcdabcd'가 반복문자열이라고 볼수도 있다. S[:8]*1 + S[:7]
- 'abcdabcdabcd'가 반복문자열이라고 볼수도 있다. S[:12]*1 + S[:3]
- 'abcdabcdabcdabc'가 반복(?)된다고도 우길수도 있긴 할텐데.. 이건 제외시키자.. '반복'은 아니잖아
- S=abaaba 이경우는?
- 'aba' 기준 : S[:3]*2 ⇒ 이렇게 뒷부분이 없으면 완전반복형태라고 부르자 (내가 만든말이다)
- 'abaab' 기준 : S[:5]*1 + S[:1]
- S=aaaa 이경우는?
- S[:1]*4
- S[:2]*2
- S[:3]*1 + S[:1]
- S=abc?
- 반복 없음
- 자, 이제 바로 가장 중요한 내용. 잘 기억하자.
- 길이 l짜리 반복문자열이 있다는 것 (S = S[:l]*n + S[:m], l>m) 은 S[:m] 이 border이라는것과 동치이다.
- 길이 x짜리 border가 있다면, 길이 l=N-x 짜리의 반복문자열이 존재한다. n=N//l, m=N%l 이 된다.
- 이제 반복문자열 관련된 태스크들을, 위에서 쓴 border 관련 해결법을 사용해서 풀수 있다.
- 가장 작은 반복문자열을 찾으려면, (S를 제외한) 가장 긴 border를 찾으면 된다. 이 border의 길이는 fail[N-1]이니까, l= N-fail[N-1] 이다.
- 관련문제: 광고
- S의 모든 반복표현을 찾으려면, S의 모든 border를 찾으면 된다.
- S를 완전반복형태로 표현할수 있는 필요충분조건은, 가장 짧은 반복문자열 l에 대해서 완전반복형태가 되는것이다. 즉 N%(N-fail[N-1])==0 이다
- 하지만! S가 완전반복형태인지를 알아보는 것만이 목적이라면 굳이 가장 짧은 반복문자열을 구할 필요는 없다. 그냥 (S+S)에서 S를 검색해보면 된다. 맨 앞이나 맨 뒤가 아닌 다른 위치에서 매칭이 되면, 반복형태이다. 이때 매칭된 위치 = 가장 짧은 반복문자열의 길이이다
i = (s+s).find(s, 1) rep_len = 0 if i == -1 else i
- 관련문제: 문자열 제곱
ps/문자열.txt · 마지막으로 수정됨: 2023/05/27 14:47 저자 teferi
토론