본문 바로가기

라이브러리9

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.
BFS #include using namespace std; typedef long long ll; typedef pair pii; int R, C; int board[100][100]; int dir8[2][8]{ {0, -1, 0, 1, -1, -1, 1, 1}, {1, 0, -1, 0, 1, -1, -1, 1} }; bool dup[100][100]; void bfs(pii init) { int cr, cc, nr, nc; queue que; dup[init.first][init.second] = true; for (que.push(init); !que.empty(); que.pop()) { tie(cr, cc) = que.front(); for (int i = 0; i < 4; ++i) { nr = cr.. 2020. 12. 13.
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.