API tools faq
paste
Advertisement
newb_ie

Library v2.0

newb_ie
Oct 14th, 2021
216
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 23.61 KB | None | 0 0
raw download clone embed print report
  1. == == == == == =
  2. [TEMPLATES]
  3. == == == == == =
  4. Direction array :
  5. int dx[8] = {1, 0, -1, 0, -1, -1, 1, 1};
  6. int dy[8] = {0, 1, 0, -1, -1, 1, -1, 1};
  7. //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  8. #define filein freopen ("in.txt", "r", stdin)
  9. #define fileout freopen ("out.txt", "w", stdout)
  10. == == ==
  11. [PBDS]
  12. == == ==
  13. #include <ext/pb_ds/assoc_container.hpp>
  14. #include <ext/pb_ds/tree_policy.hpp>
  15. using namespace __gnu_pbds;
  16. typedef tree<long long, null_type, less_equal<long long>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
  17.  
  18. freopen ("input.txt", "r", stdin);
  19. freopen ("output.txt", "w", stdout);
  20. template<typename T> istream &operator>>(istream &is, vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
  21. template<typename T> ostream &operator<<(ostream &os, const vector<T> &vec) { os << "["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
  22. template<typename T> ostream &operator<<(ostream &os, const deque<T> &vec) { os << "deq["; for (auto v : vec) os << v << ", "; os << "]"; return os; }
  23. template<typename T> ostream &operator<<(ostream &os, const set<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  24. template<typename T> ostream &operator<<(ostream &os, const unordered_set<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  25. template<typename T> ostream &operator<<(ostream &os, const multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  26. template<typename T> ostream &operator<<(ostream &os, const unordered_multiset<T> &vec) { os << "{"; for (auto v : vec) os << v << ", "; os << "}"; return os; }
  27. template<typename T1, typename T2> ostream &operator<<(ostream &os, const pair<T1, T2> &pa) { os << "(" << pa.first << ", " << pa.second << ")"; return os; }
  28. template<typename TK, typename TV> ostream &operator<<(ostream &os, const map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
  29. template<typename TK, typename TV> ostream &operator<<(ostream &os, const unordered_map<TK, TV> &mp) { os << "{"; for (auto v : mp) os << v.first << ": " << v.second << ", "; os << "}"; return os; }
  30. template<typename T> void ndarray(vector<T> &vec, int len) { vec.resize(len); }
  31. template<typename T, typename... Args> void ndarray(vector<T> &vec, int len, Args... args) { vec.resize(len); for (auto &v : vec) ndarray(v, args...); }
  32. template<typename T> bool chmax(T &m, const T q) { if (m < q) {m = q; return true;} else return false; }
  33. template<typename T> bool chmin(T &m, const T q) { if (q < m) {m = q; return true;} else return false; }
  34. template<typename T1, typename T2> pair<T1, T2> operator+(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first + r.first, l.second + r.second); }
  35. template<typename T1, typename T2> pair<T1, T2> operator-(const pair<T1, T2> &l, const pair<T1, T2> &r) { return make_pair(l.first - r.first, l.second - r.second); }
  36. == == == == == == == == == == == =
  37. [ BITWISE FUNCTIONS ]
  38. == == == == == == == == == == == =
  39.  
  40. int set_bit(int n, int pos) {return n = (n | (1 << pos));}
  41. int reset_bit(int n, int pos) {return n = n & ~(1 << pos);}
  42. bool check_bit(int n, int pos) {return n = n & (1 << pos);}
  43.  
  44. void add (int & s, int n) {
  45. if ((s & (1 << (n - 1)))) return;
  46. s ^= (1 << (n - 1));
  47. }
  48.  
  49. void remove (int & s, int n) {
  50. if (!(s & (1 << (n - 1)))) return;
  51. s ^= (1 << (n - 1));
  52. }
  53.  
  54. void display (int s) {
  55. for (int bit = 0; bit < 9; ++bit) {
  56. if (s & (1 << bit)) {
  57. cout << bit + 1 << ' ';
  58. }
  59. }
  60. cout << '\n';
  61. }
  62. == == == == == == == == == == == =
  63. [NUMBER THEORY SECTION]
  64. == == == == == == == == == == == =
  65.  
  66. /*
  67. Fibonacchi
  68. */
  69.  
  70. long long Fibo (long long n) {
  71. //res[-1] = 0,res[0] = res[1] = 1;
  72. //check fibo of n, cout << Fibo(n - 1);
  73. if (res.find(n) != res.end()) {
  74. return res[n];
  75. }
  76. if (n % 2 == 0) {
  77. return res[n] = (Fibo(n / 2) * Fibo(n / 2) + Fibo(n / 2 - 1) * Fibo(n / 2 - 1)) % mod;
  78. } else {
  79. return res[n] = (Fibo(n / 2) * Fibo(n / 2 + 1) + Fibo(n / 2 - 1) * Fibo(n / 2)) % mod;
  80. }
  81. }
  82.  
  83. /*
  84. GCD & LCM Template
  85. */
  86.  
  87. template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a % b) : a); }
  88. template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
  89.  
  90. /*
  91. Moduler Arithmetic
  92. */
  93. inline void normal(long long &a) { a %= mod; (a < 0) && (a += mod); }
  94. inline long long modMul(long long a, long long b) { a %= mod, b %= mod; normal(a), normal(b); return (a * b) % mod; }
  95. inline long long modAdd(long long a, long long b) { a %= mod, b %= mod; normal(a), normal(b); return (a + b) % mod; }
  96. inline long long modSub(long long a, long long b) { a %= mod, b %= mod; normal(a), normal(b); a -= b; normal(a); return a; }
  97. inline long long modPow(long long b, long long p) { long long r = 1; while (p) { if (p & 1) r = modMul(r, b); b = modMul(b, b); p >>= 1; } return r; }
  98. inline long long modInverse(long long a) { return modPow(a, mod - 2); }
  99. inline long long modDiv(long long a, long long b) { return modMul(a, modInverse(b)); }
  100.  
  101. == == == == == == =
  102. [MOD Inverse]
  103. == == == == == == =
  104.  
  105.  
  106. == == == == == == ==
  107. [MATH FORMULA]
  108. == == == == == == ==
  109. //sum of (n)
  110. int sum = n * (n + 1) / 2;
  111. //sum of(n^2)
  112. int sum = ((n * (n + 1)) * (2 * n + 1)) / 6;
  113. //sum of range
  114. sum_of_range = n * ((r - l + 1) * (l + r)) / 2;
  115. /*
  116. Bitwise Sieve_of_Eratosthenes
  117. */
  118. const int maxN = 10000;
  119. long long isVisited[maxN / 64 + 200];
  120. vector<int> primes;
  121. void Sieve_of_Eratosthenes(int limit) {
  122. limit += 100;
  123. for (long long i = 3; i <= sqrt(limit) ; i += 2) {
  124. if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
  125. for (long long j = i * i; j <= limit; j += 2 * i) {
  126. isVisited[j / 64] |= (1LL << (j % 64));
  127. }
  128. }
  129. }
  130. primes.push_back(2);
  131. for (long long i = 3; i <= limit; i += 2) {
  132. if (!(isVisited[i / 64] & (1LL << (i % 64)))) {
  133. primes.push_back(i);
  134. }
  135. }
  136. }
  137.  
  138. /*
  139. IS PRIME Function(Bitwise Seive)
  140. */
  141. bool is_prime(int n) {
  142. if (n < 2) return false;
  143. if (n == 2) return true;
  144. if (n % 2 == 0) return false;
  145. if (!(isVisited[n / 64] & (1LL << (n % 64)))) return true;
  146. return false;
  147. }
  148.  
  149.  
  150. /*
  151. Generate All Divisors of a Number Using Prime Factorization
  152. */
  153.  
  154. //Seive CODE Here
  155.  
  156. vector<int> setDivisors(int n, int i, vector<int> & divisors, vector<pair<int, int>> factors) {
  157. int j, x, k;
  158. for (j = i; j < (int) factors.size(); j++) {
  159. x = factors[j].first * n;
  160. for (k = 0; k < factors[j].second; k++) {
  161. divisors.push_back(x);
  162. setDivisors(x, j + 1, divisors, factors);
  163. x *= factors[j].first;
  164. }
  165. }
  166. return divisors;
  167. }
  168. vector<int> PF(int n) {
  169. int x = n;
  170. vector<pair<int, int>> factors;
  171. for (auto i : primes) {
  172. if (i * i > n) {
  173. break;
  174. }
  175. if (n % i == 0) {
  176. int count = 0;
  177. while (n % i == 0) {
  178. n /= i;
  179. count += 1;
  180. }
  181. factors.push_back(make_pair(i, count));
  182. }
  183. }
  184. if (n > 1) {
  185. factors.push_back(make_pair(n, 1));
  186. }
  187. vector<int> d = {1};
  188. vector<int> divisors = setDivisors(1, 0, d, factors);
  189. return divisors;
  190. }
  191.  
  192. /*
  193. Generate Divisors in Sqrt(n) Time
  194. */
  195. vector<int> GEN_DIVS_SQRT(int n) {
  196. vector<int> divisors;
  197. for (int i = 1; i * i <= n; i++) {
  198. if (n % i == 0) {
  199. if (n / i != i) {
  200. divisors.push_back(n / i);
  201. }
  202. divisors.push_back(i);
  203. }
  204. }
  205. return divisors;
  206. }
  207.  
  208. /*
  209. Count Divisors Using Prime Factorization
  210. */
  211. int COUNT_DIVISORS(int n) {
  212. int divisors = 1;
  213. for (auto i : primes) {
  214. if (n % i == 0) {
  215. if (i * i > n) {
  216. return divisors;
  217. }
  218. int count = 1;
  219. while (n % i == 0) {
  220. n /= i;
  221. count += 1;
  222. }
  223. divisors *= count;
  224. }
  225. }
  226. return divisors;
  227. }
  228.  
  229. == == == == == == == == == =
  230. [ BIG MOD SECTION ]
  231. == == == == == == == == == =
  232. //divide a long number(like 10^18)
  233. int Quotient(string s, int m) {
  234. int count = 0;
  235. for (int i = 0; i < (int) s.size(); i++) {
  236. count = (count * 10 + (s[i] - 48)) % m;
  237. }
  238. return count;
  239. }
  240.  
  241. == == == == == == == == == == == == == == =
  242. [Range Minimum Query SECTION]
  243. == == == == == == == == == == == == == == =
  244. == == == == == == == == == == == == == ==
  245. [SEGMENT TREE (SUM) EDITABLE]
  246. == == == == == == == == == == == == == ==
  247. const int maxN = 10000 * 4 + 1;
  248. int input[maxN / 4], tree[maxN];
  249. void buildTree(int idx, int start, int end) {
  250. if (start == end) {
  251. tree[idx] = input[start];
  252. } else {
  253. int mid = start + (end - start) / 2;
  254. buildTree(idx * 2, start, mid);
  255. buildTree(idx * 2 + 1, mid + 1, end);
  256. tree[idx] = tree[2 * idx] + tree[2 * idx + 1];
  257. }
  258. }
  259. int query(int idx, int start, int end, int l, int r) {
  260. if (l > end or r < start) {
  261. return 0;
  262. }
  263. if (start >= l and end <= r) {
  264. return tree[idx];
  265. }
  266. int mid = start + (end - start) / 2;
  267. return query(idx * 2, start, mid, l, r) + query(idx * 2 + 1, mid + 1, end, l, r);
  268. }
  269. void update(int idx, int l, int r, int pos, int val) {
  270. set<char> res;
  271. if (l == r) {
  272. tree[idx] = val;
  273. } else {
  274. int mid = l + (r - l) / 2;
  275. if (pos <= mid) {
  276. update(idx * 2, l, mid, pos, val);
  277. } else {
  278. update(idx * 2 + 1, mid + 1, r, pos, val);
  279. }
  280. res.insert(tree[idx * 2].begin(), tree[idx * 2].end());
  281. res.isnert(Tree[idx * 2 + 1].begin(), tree[idx * 2].end());
  282. tree[idx] = res;
  283. }
  284. }
  285. == == == == == == == == == == == == ==
  286. [DIS - JOINT SET UNION (DSU)]
  287. == == == == == == == == == == == == ==
  288.  
  289.  
  290. const int maxN = 26;
  291. int p[maxN],r[maxN];
  292. bool has[maxN];
  293.  
  294. int __find__ (int a) {
  295. return p[a] = (p[a] == a ? a : __find__(p[a]));
  296. }
  297.  
  298. void __union__ (int a,int b) {
  299. a = __find__(a);
  300. b = __find__(b);
  301. if (r[a] == r[b]) ++r[a];
  302. if (r[a] > r[b]) p[b] = a;
  303. else p[a] = b;
  304. }
  305.  
  306. const int maxN = 100100;
  307. int parent[maxN];
  308.  
  309. int Find(int child) {
  310. if (parent[child] < 0) {
  311. return child;
  312. }
  313. return parent[child] = Find(parent[child]);
  314. }
  315.  
  316. void Union(int a, int b) {
  317. parent[a] += parent[b];
  318. parent[b] = a;
  319. }
  320. == == == == == == == == == =
  321. [STRING ALGORITHMS]
  322. == == == == == == == == == =
  323. == == == == == == == == == == == == =
  324. [KMP SEARCH ALGORITHM]
  325. [COMPLEXITY : O(N + M) ]
  326. == == == == == == == == == == == == =
  327.  
  328. vector<int> lps_array(string p) {
  329. vector<int> lps((int) p.size());
  330. int i = 1, idx = 0;
  331. while (i < (int) p.size()) {
  332. if (p[idx] == p[i]) {
  333. lps[i] = idx + 1;
  334. idx += 1, i += 1;
  335. } else {
  336. if (idx != 0) {
  337. idx = lps[idx - 1];
  338. } else {
  339. lps[i] = 0;
  340. i += 1;
  341. }
  342. }
  343. }
  344. return lps;
  345. }
  346. void kmp(string s, string p) {
  347. vector<int> lps = lps_array(p);
  348. int i = 0, j = 0;
  349. while (i < (int) s.size()) {
  350. if (s[i] == p[j]) {
  351. i += 1, j += 1;
  352. } else {
  353. if (j != 0) {
  354. j = lps[j - 1];
  355. } else {
  356. i += 1;
  357. }
  358. }
  359. if (j == (int) p.size()) {
  360. cout << i - (int) p.size() << "\n";
  361. }
  362. }
  363. }
  364. == == == == == == ==
  365. [GRAPH THEORY]
  366. == == == == == == ==
  367. /*
  368. Bipartile(Also Known as Two Coloring Problem) Checking
  369. */
  370. const int maxN = 101;
  371. vector<int> adj[maxN];
  372. bool isVisited[maxN];
  373. int color[maxN];
  374. int Two_Coloring(int node, int col) {
  375. isVisited[node] = true;
  376. color[node] = col;
  377. for (auto u : adj[node]) {
  378. if (!isVisited[node]) {
  379. if (!Two_Coloring(u, col ^ 1)) {
  380. return false;
  381. }
  382. } else {
  383. if (color[node] == color[u`]) {
  384. return false;
  385. }
  386. }
  387. }
  388. return true;
  389. }
  390.  
  391. int dx[4] = {1, 0, -1, 0};
  392. int dy[4] = {0, 1, 0, -1};
  393.  
  394. /*
  395. Cycle Detection / Finding Back Edge
  396. */
  397. const int maxN = 101;
  398. vector<int> adj[maxN];
  399. bool isVisited[maxN];
  400. bool CycleDetection(int node, int parent) {
  401. isVisited[node] = true;
  402. for (auto u : adj[node]) {
  403. if (!isVisited[u]) {
  404. if (CycleDetection(u, node)) {
  405. return true;
  406. }
  407. }
  408. } else {
  409. if (u != parent) {
  410. return true;
  411. }
  412. }
  413. }
  414. return false;
  415. }
  416.  
  417. /*
  418. In and Out Time of a Node
  419. */
  420. const int maxN = 101;
  421. vector<int> adj[maxN];
  422. bool isVisited[maxN];
  423. int InTime[maxN], OutTime[maxN];
  424. int Timer = 1;
  425. void InOutTime(int node) {
  426. isVisited[node] = true;
  427. InTime[node] = Timer++;
  428. for (auto u : adj[node]) {
  429. if (!isVisited[u]) {
  430. InOutTime(u);
  431. }
  432. }
  433. OutTime[node] = Timer++;
  434. }
  435.  
  436. /*
  437. BFS : Breath First Search
  438. */
  439. const int maxN = 101;
  440. vector<int> adj[maxN];
  441. bool isVisited[maxN];
  442. int dist[maxN];
  443. void BFS(int node) {
  444. queue<int> q;
  445. q.push(node);
  446. isVisited[node] = true;
  447. dist[node] = 0;
  448. while (!q.empty()) {
  449. int v = q.front();
  450. q.pop();
  451. for (auto u : adj[v]) {
  452. if (!isVisited[u]) {
  453. isVisited[u] = true;
  454. dist[u] = dist[v] + 1;
  455. q.push(u);
  456. }
  457. }
  458. }
  459. }
  460.  
  461. /*
  462. Diameter of a Tree Using DFS
  463. */
  464.  
  465. const int maxN = 10100;
  466. int max_distance, max_node;
  467. vector<int> adj[maxN];
  468. bool isVisited[maxN];
  469. void diameter(int node, int distance) {
  470. isVisited[node] = true;
  471. if (distance > max_distance) {
  472. max_distance = distance;
  473. max_node = node; `
  474. }
  475. for (int child : adj[node]) {
  476. if (!isVisited[child]) {
  477. dfs(child, distance + 1);
  478. }
  479. }
  480. }
  481.  
  482. /*
  483. Diameter of a Tree Using BFS
  484. */
  485. const int maxN = 10100;
  486. vector<int> adj[maxN];
  487. bool isVisited[maxN];
  488. int dist[maxN];
  489. pair<int, int> BFS(int node, int distance) {
  490. int max_node = -1, max_dist = -1;
  491. queue<int> q;
  492. q.push(node);
  493. dist[node] = distance;
  494. while (!q.empty()) {
  495. int v = q.front();
  496. q.pop();
  497. for (auto u : adj[v]) {
  498. if (!isVisited[u]) {
  499. q.push(u);
  500. isVisited[u] = true;
  501. dist[u] = dist[v] + 1;
  502. if (dist[u] > max_dist) {
  503. max_dist = dist[u];
  504. max_node = u;
  505. }
  506. }
  507. }
  508. }
  509. return {max_node, max_dist};
  510. }
  511. /* Main Functon (DFS) */
  512. max_distance = -1;
  513. dfs(1, 0);
  514. for (int i = 1; i <= n; i++) {
  515. isVisited[i] = false;
  516. }
  517. max_distance = -1;
  518. dfs(max_node, 0);
  519. cout << max_distance << "\n";
  520.  
  521. /* Main Function (BFS) */
  522. pair<int, int> node = BFS(1, 0);
  523. for (int i = 1; i <= n; i++) {
  524. isVisited[i] = false;
  525. dist[i] = 0;
  526. }
  527. node = BFS(node.first, 0);
  528. cout << node.second << "\n";
  529.  
  530. /*
  531. Calculating SUbtree size using dfs in O(n) Time
  532. */
  533.  
  534. const int maxN = 101;
  535. vector<int> adj[maxN];
  536. bool isVisited[maxN];
  537. int subTreeSize[maxN];
  538. int dfs(int node) {
  539. isVisited[node] = true;
  540. int count = 1;
  541. for (auto child : adj[node]) {
  542. if (!isVisited[child]) {
  543. count += dfs(child);
  544. }
  545. }
  546. subTreeSize[node] = count;
  547. }
  548.  
  549. /*
  550. Find Bridges Using DFS
  551. */
  552.  
  553. const int maxN = 101;
  554. const int maxN = 101;
  555. vector<int> adj[maxN];
  556. bool visited[maxN];
  557. int in[maxN], low[maxN];
  558. int timer = 0;
  559. void dfs(int node, int parent) {
  560. visited[node] = true;
  561. in[node] = low[node] = timer++;
  562. for (auto child : adj[node]) {
  563. if (child == parent) {
  564. continue;
  565. }
  566. if (visited[child]) {
  567. low[node] = min(low[node], in[child]);
  568. } else {
  569. dfs(child, node);
  570. if (low[child] > in[node]) {
  571. cout << node << " -> " << child << " Is a Bridge\n";
  572. }
  573. low[node] = min(low[node], low[child]);
  574. }
  575. }
  576. }
  577.  
  578. /*
  579. Build Suffix Array (basic)
  580. */
  581.  
  582. #include<bits/stdc++.h>
  583. using namespace std;
  584.  
  585. int main () {
  586. ios::sync_with_stdio(false);
  587. cin.tie(nullptr);
  588. cout.tie(nullptr);
  589. int T = 1;
  590. //~ cin >> T;
  591. for (int t = 1; t <= T; ++t) {
  592. string s;
  593. cin >> s;
  594. s += '$';
  595. int n = s.size();
  596. int order[n]; // order
  597. int class_[n]; // equivalent class
  598. pair<char, int> pos[n]; // position
  599. for (int i = 0; i < n; ++i) {
  600. pos[i] = make_pair(s[i], i);
  601. }
  602. sort(pos, pos + n);
  603. for (int i = 0; i < n; ++i) {
  604. order[i] = pos[i].second;
  605. }
  606. class_[order[0]] = 0;
  607. for (int i = 1; i < n; ++i) {
  608. if (pos[i].first == pos[i - 1].first) {
  609. class_[order[i]] = class_[order[i - 1]];
  610. } else {
  611. class_[order[i]] = class_[order[i - 1]] + 1;
  612. }
  613. }
  614. int k = 0;
  615. while ((1 << k) < n) {
  616. pair<pair<int, int>, int> suf[n]; //positon array
  617. for (int i = 0; i < n; ++i) {
  618. suf[i] = make_pair(make_pair(class_[i], class_[(i + (1 << k)) % n]), i);
  619. }
  620. sort(suf, suf + n);
  621. for (int i = 0; i < n; ++i) {
  622. order[i] = suf[i].second;
  623. }
  624. class_[order[0]] = 0; // first class to be order[0] = 0
  625. for (int i = 1; i < n; ++i) {
  626. if (suf[i].first == suf[i - 1].first) {
  627. class_[order[i]] = class_[order[i - 1]];
  628. } else {
  629. class_[order[i]] = class_[order[i - 1]] + 1;
  630. }
  631. }
  632. k += 1;
  633. }
  634. for (int i = 0; i < n; ++i) {
  635. cout << order[i] << " ";
  636. }
  637. }
  638. }
  639.  
  640.  
  641. //[Count Set Bits]
  642. int count = 0;
  643. while (n) {
  644. count += (n & 1);
  645. n >>= 1;
  646. }
  647.  
  648. == == == == == == =
  649. [Z Algorithm]
  650. == == == == == == =
  651. vector<int> z_algo (string s) {
  652. int n = (int) s.size();
  653. int l = 0, r = 0;
  654. vector<int> z(n);
  655. for (int i = 1; i < n; ++i) {
  656. if (i > r) {
  657. l = r = i;
  658. while (r < n and s[r] == s[r - l]) {
  659. ++r;
  660. }
  661. z[i] = r - l;
  662. --r;
  663. } else {
  664. if (i + z[i - l] <= r) {
  665. z[i] = z[i - l];
  666. } else {
  667. l = i;
  668. while (r < n and s[r] == s[r - l]) {
  669. ++r;
  670. }
  671. z[i] = r - l;
  672. --r;
  673. }
  674. }
  675. }
  676. return z;
  677. }
  678.  
  679. int main () {
  680. ios::sync_with_stdio(false);
  681. cin.tie(nullptr);
  682. cout.tie(nullptr);
  683. int T = 1;
  684. //~ cin >> T;
  685. for (int test_case = 1; test_case <= T; ++test_case) {
  686. string s, t;
  687. cin >> s >> t;
  688. string total = t + "$" + s;
  689. vector<int> z = z_algo(total);
  690. for (int i = 0; i < (int) z.size(); ++i) {
  691. if (z[i] == (int) t.size()) {
  692. cout << i - (int) t.size() - 1 << "\n";
  693. }
  694. }
  695. }
  696. //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  697. }
  698.  
  699. == == == == == ==
  700. [BITMASK DP]
  701. == == == == == ==
  702. #include<bits/stdc++.h>
  703. using namespace std;
  704.  
  705. int mem[1000][1030];
  706.  
  707. bool check (int mask) {
  708. return (bool) (mask & ((1 << 10) - 1));
  709. }
  710.  
  711. int solve (int pos, int n, int mask) {
  712. if (pos >= n) {
  713. return check(mask);
  714. }
  715. if (mem[pos][mask] != -1) {
  716. return mem[pos][mask];
  717. }
  718. int res = 0;
  719. for (int i = (pos == 0 ? 1 : pos); i <= 9; ++i) {
  720. res += solve (pos + 1, n, mask | (1 << pos));
  721. }
  722. return mem[pos][mask] = res;
  723. }
  724.  
  725. int main () {
  726. ios::sync_with_stdio(false);
  727. cin.tie(nullptr);
  728. cout.tie(nullptr);
  729. int T = 1;
  730. //~ cin >> T;
  731. for (int test_case = 1; test_case <= T; ++test_case) {
  732. memset(mem, -1, sizeof(mem));
  733. int n;
  734. cin >> n;
  735. cout << solve (1, n, 0) << "\n";
  736. }
  737. //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  738. }
  739.  
  740. == == == == ==
  741. [DIJKSTRA]
  742. == == == == ==
  743.  
  744. /*
  745. ======================
  746. [ ___T_ ]
  747. [ | 6=6 | =>HI :-)]
  748. [ |__o__| ]
  749. [ >===]__o[===< ]
  750. [ [o__] ]
  751. [ .". ]
  752. [ |_| ]
  753. [ ]
  754. ======================
  755. */
  756.  
  757. #include<bits/stdc++.h>
  758. using namespace std;
  759.  
  760. const int maxN = 2 * 1e5;
  761. vector<pair<long long, long long>> adj[maxN];
  762. long long dist[maxN];
  763.  
  764. void dijkstra (int source, int n) {
  765. for (int i = 1; i <= n; ++i) dist[i] = LLONG_MAX;
  766. dist[source] = 0;
  767. priority_queue<pair<long long, long long>, vector<pair<long long, long long>>, greater<pair<long long, long long>>> pq;
  768. pq.push(make_pair(0, source));
  769.  
  770. while (!pq.empty()) {
  771. long long u = pq.top().second;
  772. long long current_dist = pq.top().first;
  773. pq.pop();
  774.  
  775. if (dist[u] < current_dist) {
  776. continue;
  777. }
  778.  
  779. for (pair<long long, long long> v : adj[u]) {
  780. if (current_dist + v.second < dist[v.first]) {
  781. dist[v.first] = current_dist + v.second;
  782. pq.push(make_pair(dist[v.first], v.first));
  783. }
  784. }
  785. }
  786. }
  787.  
  788. int main () {
  789. ios::sync_with_stdio(false);
  790. cin.tie(nullptr);
  791. cout.tie(nullptr);
  792. int T = 1;
  793. //~ cin >> T;
  794. for (int test_case = 1; test_case <= T; ++test_case) {
  795. int n, m;
  796. cin >> n >> m;
  797. for (int i = 1; i <= m; ++i) {
  798. long long u, v, w;
  799. cin >> u >> v >> w;
  800. adj[u].push_back(make_pair(v, w));
  801. }
  802. dijkstra(1, n);
  803. for (int i = 1; i <= n; ++i) {
  804. cout << dist[i] << " ";
  805. }
  806. }
  807. //cerr << "Time elapsed :" << clock() * 1000.0 / CLOCKS_PER_SEC << " ms" << '\n';
  808. }
  809.  
  810.  
  811. Sparse Table
  812.  
  813. const int maxN = 1e5 + 10;
  814. long long st[maxN][20];
  815. int bin_log[maxN];
  816. long long input[maxN];
  817.  
  818. void sparseTable (int n) {
  819. for (int i = 2; i <= n; ++i) bin_log[i] = bin_log[i / 2] + 1;
  820. for (int i = 0; i < n; ++i) st[i][0] = input[i];
  821. for (int j = 1; j < 20; ++j) {
  822. for (int i = 0; i + (1 << j) - 1 < n; ++i) {
  823. st[i][j] = max(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
  824. }
  825. }
  826. //for query min_max
  827. /*
  828. int l,r;
  829. cin >> l >> r;
  830. int j = bin_log[r - l + 1];
  831. cout << min(st[l][j],st[r - (1 << j) + 1][j]) << '\n';
  832. */
  833. }
  834.  
  835.  
  836. String Hashing
  837.  
  838. int single_hash (const string & s) {
  839. const int p = 31;
  840. const int m = 1e9 + 9;
  841. long long hash_value = 0;
  842. long long p_pow = 1;
  843. for (char c : s) {
  844. hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
  845. p_pow = (p_pow * p) % m;
  846. }
  847. return hash_value;
  848. }
  849.  
  850. int compute_hash (const string & s) {
  851. int n = (int) s.size();
  852. const int p = 31;
  853. const int m = 1e9 + 9;
  854. vector<long long> p_pow(n);
  855. p_pow[0] = 1;
  856. for (int i= 1; i < n; ++i) p_pow[i] = (p_pow[i - 1] * p) % m;
  857. vector<long long> h(n + 1,0);
  858. for (int i = 0; i < n; ++i) {
  859. h[i + 1] = (h[i] + (s[i] - 'a' + 1) * p_pow[i]) % m;
  860. }
  861. //number of different substring(for small length)
  862. int cnt = 0;
  863. for (int l = 1; l <= n; ++l) {
  864. set<long long> hs;
  865. for (int i = 0; i <= n - l; ++i) {
  866. long long cur_h = (h[i + l] + m - h[i]) % m;
  867. cur_h = (cur_h * p_pow[n - i - 1]) % m;
  868. hs.insert(cur_h);
  869. }
  870. cnt += (int) hs.size();
  871. }
  872. return cnt;
  873. }
  874.  
  875.  
  876.  
  877. const int maxN = 2100;
  878. const long long p = 31;
  879. const long long m = 1e9 + 7;
  880. long long h[maxN],inv[maxN];
  881.  
  882. long long bin_pow (long long a,long long b) {
  883. a %= m;
  884. long long res = 1;
  885. while (b > 0) {
  886. if (b & 1) res = res * a % m;
  887. a = a * a % m;
  888. b >>= 1;
  889. }
  890. return res;
  891. }
  892.  
  893. void compute_hash (string & s) {
  894. long long p_pow = 1;
  895. inv[0] = 1;
  896. h[0] = s[0] - 'a' + 1;
  897. for (int i = 1; i < (int) s.size(); ++i) {
  898. p_pow = (p_pow * p) % m;
  899. inv[i] = bin_pow(p_pow,m - 2);
  900. h[i] = (h[i - 1] + (s[i] - 'a' + 1) * p_pow) % m;
  901. }
  902. }
  903.  
  904. long long sub_hash (int l,int r) {
  905. long long res = h[r];
  906. if (l > 0) res -= h[l - 1];
  907. res = (res * inv[l]) % m;
  908. if (res < 0) res = (res + m) % m;
  909. return res;
  910. }
  911.  
  912. long long single_hash (string & s) {
  913. long long hash_value = 0;
  914. long long p_pow = 1;
  915. for (char c : s) {
  916. hash_value = (hash_value + (c - 'a' + 1) * p_pow) % m;
  917. p_pow = (p_pow * p) % m;
  918. }
  919. return hash_value;
  920. }
  921.  
  922.  
  923. struct StringHash {
  924. const long long p = 31;
  925. const long long m = 1e9 + 7;
  926. vector<long long> h;
  927. vector<long long> inv;
  928. inline void init (string & s) {
  929. h.resize((int) s.size());
  930. inv.resize((int) s.size());
  931. compute_hash(s);
  932. }
  933. inline long long bin_pow (long long a,long long b) {
  934. a %= m;
  935. long long res = 1;
  936. while (b > 0) {
  937. if (b & 1) res = res * a % m;
  938. a = a * a % m;
  939. b >>= 1;
  940. }
  941. return res;
  942. }
  943. inline void compute_hash (string & s) {
  944. long long p_pow = 1;
  945. inv[0] = 1;
  946. h[0] = s[0] - 'a' + 1;
  947. for (int i = 1; i < (int) s.size(); ++i) {
  948. p_pow = (p_pow * p) % m;
  949. inv[i] = bin_pow(p_pow,m - 2);
  950. h[i] = (h[i - 1] + (s[i] - 'a' + 1) * p_pow) % m;
  951. }
  952. }
  953. inline long long sub_hash (int l,int r) {
  954. long long res = h[r];
  955. if (l > 0) res -= h[l - 1];
  956. res = (res * inv[l]) % m;
  957. if (res < 0) res += m;
  958. return res;
  959. }
  960. inline long long single_hash (string & s) {
  961. long long hash_value = 0;
  962. long long p_pow = 1;
  963. for (int i = 0; i < (int) s.size(); ++i) {
  964. hash_value = (hash_value + (s[i] - 'a' + 1) * p_pow) % m;
  965. p_pow = (p_pow * p) % m;
  966. }
  967. return hash_value;
  968. }
  969. };
  970.  
  971.  
  972. //sparse table min
  973.  
  974. const int maxN = 2e5 + 100;
  975. int64_t st[maxN][20];
  976. int bin_log[maxN];
  977. int64_t input[maxN];
  978.  
  979. void sparseTable (int n) {
  980. for (int i = 2; i <= n; ++i) bin_log[i] = bin_log[i / 2] + 1;
  981. for (int i = 0; i < n; ++i) st[i][0] = input[i];
  982. for (int j = 1; j < 20; ++j) {
  983. for (int i = 0; i + (1 << j) - 1 < n; ++i) {
  984. st[i][j] = min(st[i][j - 1],st[i + (1 << (j - 1))][j - 1]);
  985. }
  986. }
  987. }
  988.  
  989. int query (int l, int r) {
  990. //0 based idx
  991. int j = bin_log[r - l + 1];
  992. return min(st[l][j],st[r - (1 << j) + 1][j]);
  993. }
  994.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!