본문 바로가기

라이브러리7

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.
Topological Sort #include using namespace std; const int MAX = 10000 + 1; vector adj[MAX]; queue Q; int N, res; int indegree[MAX], cost[MAX], result[MAX]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> N; for (int i = 1; i > cost[i]; int K; cin >> K; for (int k = 1; k > p; adj[p].push_back(i); } if (indegree[i] == 0) { Q.push(i); result[i] = cost[i]; res = max(res, result[i]); } } for (int.. 2020. 9. 16.
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.
Floyd-Warshall #include #include #define INF 1e9 #define NODES 101 using namespace std; int N, M; // 노드 간선 수 int dist[NODES][NODES]; int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); cin >> N >> M; for (int i = 1; i > v >> w; dist[u][v] = min(dist[u][v], w); } for (int k = 1; k 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.
Dijkstra #include using namespace std; typedef pair pii; struct Dijkstra { int INF = 2147483647; int* minDist; vector* edges; Dijkstra(int n) { minDist = new int[n]; edges = new vector[n]; for (int i = 0; i < n; ++i) { minDist[i] = INF; } } void addEdge(int a, int b, int w) { edges[a].push_back({ w, b }); //edges[b].push_back({ w, a }); } void build(int base) { priority_queue pque; pque.push({ 0, base }).. 2020. 8. 6.