문자열3 Trie #include using namespace std; const int childMax = 26; const char baseChar = 'A'; struct Trie { Trie* child[childMax]; // 'A' ~ 'Z' bool isRet, isParent; Trie() { fill(child, child + childMax, nullptr); isRet = isParent = false; } ~Trie() { for (int i = 0; i < childMax; ++i) { if (child[i]) delete child[i]; } } void insert(const char* key) { if (*key == '\0') isRet = true; else { int next = *key.. 2020. 9. 4. Z 길이 $n$의 문자열 $S[0:n]$에 대하여 $Array Z[0:n]$를 $O(n)$에 구한다. $i$ $Z$ a n a n a b 0 6 a n a n a b 1 0 n a n a b 2 3 a n a b 3 0 n a b 4 1 a b 5 0 b $Z[i]$는 $S[0:]$와 $S[i:]$의 최대 공통 접두사의 길이이다. 코드는 다음과 같이 작성하였다. def getZ(s): l,r=0,0 ret=[0]*len(s) ret[0]=len(s) for i in range(1,len(s)): if i>r: l=r=i while r 2020. 8. 15. KMP from sys import stdin def input(): return stdin.readline().rstrip() def getFail(P): Plen=len(P) ret=[0]*Plen j=0 for i in range(1,Plen): while j>0 and P[i]!=P[j]: j=ret[j-1] if P[i]==P[j]: j+=1 ret[i]=j return ret def KMP(T, P): ret=[] Tlen=len(T) Plen=len(P) j=0 for i in range(Tlen): while j>0 and T[i]!=P[j]: j=fail[j-1] if T[i]==P[j]: if j==Plen-1: ret.append(str(i-Plen+2)) j=fail[j] else: j+=.. 2020. 8. 11. 이전 1 다음
