본문 바로가기

라이브러리/문자열4

Rabin karp #include #define sad std::cout.flush(), system("pause") using namespace std; using ll = long long; using pii = pair; using pll = pair; namespace rbk { const ll x = 131, md1 = 1e9+7, md2 = 1e9+9; int plen; pll d; void init(int n) { plen = n; d = {1, 1}; for (int i = 0; i < n; ++i) { d.first = (d.first * x) % md1, d.second = (d.second * x) % md2; } } pll hash(string &s, int len = 0, int b = 0) { p.. 2021. 2. 10.
Suffix Array와 LCP Array #include using namespace std; typedef long long ll; typedef pair pii; vector suffixArray, LCPArray; void getLCP(vector& sa, vector& lcpa, string& s) { int i, j, k, l = 0, m = 26, sLen = s.length(); sa.resize(sLen, 0); lcpa.resize(sLen, 0); // cnt: radix cnt | x: rank vector cnt(max(sLen, m), 0), x(sLen, 0), y(sLen, 0); for (i = 0; i < sLen; ++i) cnt[x[i] = s[i] - 'a']++; for (i = 0; i < m; ++i) .. 2020. 9. 23.
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.
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.