문자열

문자열 관련해서 PS레벨에서 알아야 할 알고리즘들은 어느정도 정해져있는 편이고, 그다지 많지 않다.
어려운 점은 어떤 문제에 어떤 알고리즘을 어떻게 적용해야 할지이다.
처음에 kmp와 z알고리즘을 공부하고서 관련 문제를 풀어보는데 언제 뭘써야 하고, 뭐가 되고 뭐가 안되고가 엄청 헷갈렸다, 어찌어찌 답은 나오더라도 과정이 머릿속에 명확하지 못하고.. 풀이를 보더라도 다른 문제에 확장이 잘 안됐다.
이게 풀이에서는 'kmp를 이렇게 이렇게 쓰면 이 문제를 풀수 있다' 주로 이런식으로만 적혀있는데.. 내가 고심한 결과 다른 문제에 적용하는 능력을 기르려면, 알고리즘에서 문제로 바로 연결되는게 아니라, 중간 단계 태스크를 추가해서 정리해야할 필요가 있다는 것을 알았다. 즉 'KMP를 쓰면 이런 것을 할수있다. 이런것을 할수 있으면 이 문제를 풀수있다' 이런식으로 정리를 해보려고 했고.. 이러면, '이런것은, z 알고리즘을 써도 할수 있다. 따라서 이 문제는 z 알고리즘으로도 풀수 있다' 이렇게 문제를 명확하게 이해하는데 큰 도움이 되었다.
그래서 나름대로 정리한 내용들을 모아보기는 하는데.. 이게 다른곳에서 이렇게 정리된것을 가져온게 아니라 내가 이해한것들을 독자적으로 정리한 내용에 가까워서 추후 언제든 수정될수 있다..

러프하게 분류한 접근 방법들

여러개의 문자열들을 갖고 뭔가를 한다
- 일단 문자열들을 트라이로 관리해보자
  - 트라이는 여러개의 문자열들을 가장 효율적으로 관리할수 있는 구조이다.
  - 문자열 셋 중에서, 특정 문자열이 있는지, 특정 prefix로 시작하는 문자열이 있는지, prefix가 가장 길게 겹치는 문자열이 뭔지 등등을 효율적으로 찾을수 있다
- 문제에 따라서는 그냥 소팅만 해놓고 거기에서 찾아서 써도 풀리는 문제도 있긴 하다.
주어진 문자열의 prefix에 관한 문제
- 주어진 문자열이 prefix에 관련된 조건을 만족하는지, 조건을 만족하는 prefix가 몇개인지, 조건을 만족하는 prefix중 가장 긴것이 뭐인지 등등.
- KMP 알고리즘의 fail 함수나 Z 알고리즘의 z 배열을 사용해볼 생각을 하자.
- 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
```
- 관련문제: 문자열 제곱

목차

문자열

러프하게 분류한 접근 방법들

Prefix 관련 태스크

각각의 prefix의 등장 횟수를 모두 세기

Border 관련 태스크

기본 테크닉

반복 찾기