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

===== 러프하게 분류한 접근 방법들 =====
  * 여러개의 문자열들을 갖고 뭔가를 한다
    * 일단 문자열들을 트라이로 관리해보자
      * 트라이는 여러개의 문자열들을 가장 효율적으로 관리할수 있는 구조이다.
      * 문자열 셋 중에서, 특정 문자열이 있는지, 특정 prefix로 시작하는 문자열이 있는지, prefix가 가장 길게 겹치는 문자열이 뭔지 등등을 효율적으로 찾을수 있다
    * 문제에 따라서는 그냥 소팅만 해놓고 거기에서 찾아서 써도 풀리는 문제도 있긴 하다.
  * 주어진 문자열의 prefix에 관한 문제
    * 주어진 문자열이 prefix에 관련된 조건을 만족하는지, 조건을 만족하는 prefix가 몇개인지, 조건을 만족하는 prefix중 가장 긴것이 뭐인지 등등.
    * [[ps:KMP 알고리즘]]의 fail 함수나 [[ps:Z 알고리즘]]의 z 배열을 사용해볼 생각을 하자. 
    * fail함수와 z배열은 할수 있는 일이 거의 비슷하다. 둘다 prefix와 일치하는 부분문자열의 정보를 갖는다. fail[i]은 i위치에서 **끝나면서** prefix와 일치하는 가장 긴 부분문자열의 길이를, z[i]는 i위치에서 **시작하면서** prefix와 일치하는 가장 긴 부분문자열의 길이를 저장한다. 대충 편한걸로 쓰면 된다.
    * 'prefix이면서 suffix인 부분문자열이...' 이런 문제가 나오면 kmp나 z로 풀수 있을 확률이 좀더 올라간다
    * 문자열의 반복패턴에 관한 문제도 이것으로 풀수 있다.
  * 주어진 문자열의 부분문자열에 관한 문제
    * prefix가 아니라 좀더 일반적인 '부분문자열'에 관한 문제가 나온다면 [[ps:접미사 배열]]를 써야 할 가능성이 크다. 
    * SA로 푸는 대표적인 문제는 서로다른 부분문자열의 갯수, 두번 이상 등장하는 가장 긴 부분문자열, 어떤 두 부분문자열의 최장접두사 찾기 등이다.
    * 이 외에도 활용여부가 무궁무진한것 같긴 하지만.. 아직 많이 접해보지는 않았다
  * 그 외에 좀더 특수한 유형에 적용되는 알고리즘들
    * [[ps:문자열 매칭]]이라면 kmp를 쓰자
    * '팰린드롬'에 관련된 문제라면 매내처 알고리즘을 생각해보자
    * 'repetition'에 관련된 문제라면 [[https://cp-algorithms.com/string/main_lorentz.html|Main-Lorentz 알고리즘]]을 써야 할수도 있다.
    * 'wildcard를 포함하는 문자열 매칭' 에 관련된 문제라면 [[https://cp-algorithms.com/algebra/fft.html#string-matching-with-wildcards|FFT]]를 써야할수도 있다.


===== Prefix 관련 태스크 =====

==== 각각의 prefix의 등장 횟수를 모두 세기 ====
  * z배열 이용
    * 가장 직관적이다. z[i]가 l이라면, i부터 시작하는 1,2,3,..,l 길이의 문자열이 모두 prefix이라는 말이고, 그러니까 길이 1짜리 prefix, 길이 2짜리 prefix, .., 길이 l짜리 prefix들의 등장횟수를 모두 1 증가시켜주면 된다. 누적합을 이용하면 간단.
    * <dkpr py>
counter = collections.Counter(z)
for i in reversed(range(len(S))):
    counter[i] += counter[i + 1]
</dkpr>
  * fail 함수 이용
    * 덜 직관적이긴 하지만, 가능하다. z배열과 달리, i에서 끝나는 l길이의 문자열이 prefix라고 해서, i에서 끝나는 l-1,l-2,..1 길이의 문자열도 prefix가 되는것은 아니다, 하지만, fail[i-1], fail[fail[i-1]],... 이 prefix가 된다는 것은 알고 있다. 이것을 이용해서 로직을 조금 더 정리하면 아래처럼 할 수 있다.
    * <dkpr py>
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
</dkpr>
  * 관련 문제: [[ps:problems:boj:13576]]

===== Border 관련 태스크 ======
  * [[https://en.wikipedia.org/wiki/Substring#Border|Border]] 는 어떤 문자열의 prefix이면서 동시에 suffix인 부분문자열을 말한다.
  * Border를 이용해서 처리되는 문자열 관련 문제들이 많다.

==== 기본 테크닉 ====
  * 가장 긴 proper Border(의 길이) 찾기 
    * fail 펑션이 있다면 : fail[-1] 
    * Z array가 있다면 :

  * Border를 모두 찾기
    * s[:l] == s[-l:] 인 l을 모두 찾는다
    * fail 펑션 이용
      * <dkpr py>    
fail = tstring.failure_table(S)
l = len(S)
border_lens = [len(S)]
while l := fail[l - 1]:
    border_lens.append(l)
</dkpr>
        * (내림차순으로 저장됨)
    * Z 배열 이용 
      * <dkpr py>
z = tstring.z_array(S)
border_lens = [i for i, z_i in enumerate(reversed(z), start=1) if i == z_i]
</dkpr>
        * (오름차순으로 저장됨)

==== 반복 찾기 ====
  * 반복..은 내가 적당히 붙인 말이라서 좀 추상적이니까 좀더 정확히 정의해보자. 문자열을 부분문자열의 반복으로 표현하는 것을 생각하자.
    * 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] 이다.
      * 관련문제: [[ps:problems:boj:1305]]
    * S의 모든 반복표현을 찾으려면, S의 모든 border를 찾으면 된다. 
  * S를 완전반복형태로 표현할수 있는 필요충분조건은, 가장 짧은 반복문자열 l에 대해서 완전반복형태가 되는것이다. 즉 N%(N-fail[N-1])==0 이다
    * 하지만! S가 완전반복형태인지를 알아보는 것만이 목적이라면 굳이 가장 짧은 반복문자열을 구할 필요는 없다. 그냥 (S+S)에서 S를 검색해보면 된다. 맨 앞이나 맨 뒤가 아닌 다른 위치에서 매칭이 되면, 반복형태이다. 이때 매칭된 위치 = 가장 짧은 반복문자열의 길이이다 
      * <dkpr py>
i = (s+s).find(s, 1)
rep_len = 0 if i == -1 else i
</dkpr>
    * 관련문제: [[ps:problems:boj:4354]]