API tools faq
paste
_no0B

Untitled

_no0B
Apr 25th, 2019
358
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 14.90 KB | None | 0 0
raw download clone embed print report
  1. /// Lexicographically Minimum String Rotation
  2. int minlex(char* str){ /// Returns the 0-based index
  3.     int i, j, k, n, len, x, y;
  4.     len = n = strlen(str), n <<= 1, i = 0, j = 1, k = 0;
  5.     while((i + k) < n && (j + k) < n) {
  6.         x = i + k >= len ? str[i + k - len] : str[i + k];
  7.         y = j + k >= len ? str[j + k - len] : str[j + k];
  8.         if(x == y) k++;
  9.         else if (x < y){
  10.             j += ++k, k = 0;
  11.             if (i >= j) j = i + 1;
  12.         }
  13.         else{
  14.             i += ++k, k = 0;
  15.             if (j >= i) i = j + 1;
  16.         }
  17.     }
  18.     return (i < j) ? i : j;
  19. }
  20. int t;
  21. char str[50010];
  22. int main(){
  23.     gets(str);
  24.     while (gets(str)){
  25.         printf("%d\n", minlex(str));
  26.     }
  27.     return 0;
  28. }
  29.  
  30.  
  31. /// Next palindrome
  32. #define MAX 100010
  33. char str[MAX];
  34. void next_palindrome(char* str){
  35.     int i, j, k, l, x, n = strlen(str), carry = 1;
  36.     for (i = 0, j = n - 1; j >= 0; i++, j--){
  37.         if (carry){
  38.             if (str[j] == 57) carry = 1, str[j] = 48;
  39.             else carry = 0, str[j]++;
  40.         }
  41.         if (i > j) str[i] = str[j];
  42.         else{
  43.             if (str[i] < str[j]) carry = 1;
  44.             str[j] = str[i];
  45.         }
  46.     }
  47.     if (carry){
  48.         str[n - 1] = 49;
  49.         for (i = n - 1; i >= 0; i--) str[i + 1] = str[i];
  50.         str[0] = 49, str[n + 1] = 0;
  51.     }
  52. }
  53. int main(){
  54.     int T = 0, t, i, j, k;
  55.     scanf("%d", &t);
  56.     while (t--){
  57.         scanf("%s", str);
  58.         next_palindrome(str);
  59.         printf("Case %d: %s\n", ++T, str);
  60.     }
  61.     return 0;
  62. }
  63.  
  64.  
  65.  
  66. /// Minimum palindromic factorization for all prefixes in O(N log N)
  67. #define MAX 1000010
  68. namespace pal{
  69.     int pl[MAX][2], gpl[MAX][2];
  70.     inline void set(int *ar, int x, int y, int z) {
  71.         ar[0] = x, ar[1] = y, ar[2] = z;
  72.     }
  73.     inline void set(int ar[][2], int i, int v) {
  74.         if (v > 0) ar[i][v & 1] = v;
  75.     }
  76.     inline void copy(int *A, int *B) {
  77.         A[0] = B[0], A[1] = B[1], A[2] = B[2];
  78.     }
  79.     inline void update(int ar[][2], int i, int v) {
  80.         if (v > 0 && (ar[i][v & 1] == -1 || ar[i][v & 1] > v)) ar[i][v & 1] = v;
  81.     }
  82.     /// Returns a vector v such that,
  83.     /// v[i] is the minimum k so that the prefix string str[0:i] can be partitioned into k disjoint palindromes
  84.     inline vector <int> factorize(const char* str){
  85.         int g[32][3], gp[32][3], gpp[32][3];
  86.         int i, j, k, l, d, u, r, x, pg = 0, pgp = 0, pgpp = 0, n = strlen(str);
  87.         clr(g), clr(gp), clr(gpp);
  88.         for (int i = 0; i < n; i++) gpl[i][0] = MAX, gpl[i][1] = MAX + 1;
  89.         for (j = 0; j < n; j++){
  90.             for (u = 0, pgp = 0; u < pg; u++){
  91.                 i = g[u][0];
  92.                 if ((i - 1) >= 0 && str[i - 1] == str[j]){
  93.                     g[u][0]--;
  94.                     copy(gp[pgp++], g[u]);
  95.                 }
  96.             }
  97.             pgpp = 0, r = -(j + 2);
  98.             for (u = 0; u < pgp; u++){
  99.                 i = gp[u][0], d = gp[u][1], k = gp[u][2];
  100.                 if ((i - r) != d){
  101.                     set(gpp[pgpp++], i, i - r, 1);
  102.                     if (k > 1) set(gpp[pgpp++], i + d, d, k - 1);
  103.                 }
  104.                 else set(gpp[pgpp++], i, d, k);
  105.                 r = i + (k - 1) * d;
  106.             }
  107.             if (j - 1 >= 0 && str[j - 1] == str[j]){
  108.                 set(gpp[pgpp++], j - 1, j - 1 - r, 1);
  109.                 r = j - 1;
  110.             }
  111.             set(gpp[pgpp++], j, j - r, 1);
  112.             int *ptr = gpp[0];
  113.             for (u = 1, pg = 0; u < pgpp; u++){
  114.                 int *x = gpp[u];
  115.                 if (x[1] == ptr[1]) ptr[2] += x[2];
  116.                 else {
  117.                     copy(g[pg++], ptr);
  118.                     ptr = x;
  119.                 }
  120.             }
  121.             copy(g[pg++], ptr);
  122.             pl[j + 1][(j & 1) ^ 1] = j + 1;
  123.             pl[j + 1][j & 1] = MAX + (j & 1);
  124.             for (u = 0; u < pg; u++){
  125.                 i = g[u][0], d = g[u][1], k = g[u][2];
  126.                 r = i + (k - 1) * d;
  127.                 update(pl, j + 1, pl[r][0] + 1);
  128.                 update(pl, j + 1, pl[r][1] + 1);
  129.                 if (k > 1) {
  130.                     update(pl, j + 1, gpl[i + 1 - d][0]);
  131.                     update(pl, j + 1, gpl[i + 1 - d][1]);
  132.                 }
  133.                 if (i + 1 >= d) {
  134.                     if (k > 1) {
  135.                         update(gpl, i + 1 - d, pl[r][0] + 1);
  136.                         update(gpl, i + 1 - d, pl[r][1] + 1);
  137.                     }
  138.                     else{
  139.                         set(gpl, i + 1 - d, pl[r][0] + 1);
  140.                         set(gpl, i + 1 - d, pl[r][1] + 1);
  141.                     }
  142.                 }
  143.             }
  144.         }
  145.         vector <int> res(n, 0);
  146.         for (i = 0; i < n; i++) res[i] = min(pl[i + 1][0], pl[i + 1][1]);
  147.         return res;
  148.     }
  149. }
  150.  
  151.  
  152.  
  153. /// rope
  154. #define MAX 50010
  155. rope <char> R[MAX];
  156. int d = 0, ye = 0, vnow = 0;
  157. char str[105], out[10000010];
  158. int main(){
  159.     int n, i, j, k, v, p, c, x, flag;
  160.     while (scanf("%d", &n) != EOF){
  161.         d = 0, vnow = 0;
  162.         while (n--){
  163.             scanf("%d", &flag);
  164.             if (flag == 1){
  165.                 scanf("%d %s", &p, str);
  166.                 p -= d, vnow++;
  167.                 R[vnow] = R[vnow - 1];
  168.                 R[vnow].insert(p, str); /// Insert string str after position p
  169.             }
  170.             if (flag == 2){
  171.                 scanf("%d %d", &p, &c);
  172.                 p -= d, c -= d, vnow++;
  173.                 R[vnow] = R[vnow - 1];
  174.                 R[vnow].erase(p - 1, c); /// Remove c characters starting at position p
  175.             }
  176.             if (flag == 3){
  177.                 scanf("%d %d %d", &v, &p, &c); /// Print c characters starting at position p in version v
  178.                 v -= d, p -= d, c -= d;
  179.                 rope <char> sub = R[v].substr(p - 1, c); /// Get the substring of c characters from position p in version v
  180.                 for (auto it: sub){
  181.                     out[ye++] = it;
  182.                     if (it == 'c') d++;
  183.                 }
  184.                 out[ye++] = 10;
  185.             }
  186.         }
  187.     }
  188.     fwrite(out, 1, ye, stdout);
  189.     return 0;
  190. }
  191.  
  192.  
  193.  
  194. /// String Hash with Segment Tree
  195. /// Allows setting range with a character, querying hash of a range in O(log n)
  196. /// String functions uses 0-based index, however segment tree uses 1-based index
  197. namespace strhash{
  198.     #define LET 10 /// Number of distinct letters in string, Set to digits [0-9] by default
  199.     #define ADD 10007 /// Just another prime added randomly to get better hash values :)
  200.     #define MAX 100010
  201.     int P[2][MAX], RD[2][LET][MAX];
  202.     int n, ar[MAX], lazy[MAX * 4];
  203.     const int MOD[] = {2078526727, 2117566807};
  204.     const int BASE[] = {1572872831, 1971536491};
  205.     void build_tree(int idx, int a, int b);
  206.     inline int getval(char ch){ /// Value of a character (without adding ADD)
  207.         return ch - 48; /// Change this for lowercase or uppercase letters
  208.     }
  209.     void precalc(){ /// Call precalc() just once in whole program
  210.         int i, j, k, d;
  211.         P[0][0] = P[1][0] = 1;
  212.         for (i = 1; i < MAX; i++){
  213.             P[0][i] = ((long long) P[0][i - 1] * BASE[0]) % MOD[0];
  214.             P[1][i] = ((long long) P[1][i - 1] * BASE[1]) % MOD[1];
  215.         }
  216.         for (i = 0; i < 2; i++){
  217.             for (d = 0; d < LET; d++){
  218.                 k = ADD + d;
  219.                 long long x = 0;
  220.                 for (j = 1; j <= MAX; j++){
  221.                     x = ((x * BASE[i]) + k) % MOD[i];
  222.                     RD[i][d][j] = x;
  223.                 }
  224.             }
  225.         }
  226.     }
  227.     void init(char* str){
  228.         n = strlen(str);
  229.         for (int i = 0; i < n; i++) ar[i + 1] = getval(str[i]) + ADD;
  230.         build_tree(1, 1, n);
  231.     }
  232.     struct Node{
  233.         int H[2];
  234.         inline Node(){
  235.         }
  236.         inline Node(int h1, int h2){
  237.             H[0] = h1, H[1] = h2;
  238.         }
  239.     } tree[MAX << 2];
  240.     inline void propagate(int idx, int a, int b){
  241.         if (lazy[idx]){
  242.             int p = (idx << 1), q = p + 1;
  243.             int c = (a + b) >> 1, d = c + 1, val = lazy[idx];
  244.             if (a != b){
  245.                 lazy[p] = lazy[q] = lazy[idx];
  246.                 tree[p] = Node(RD[0][val - ADD][c - a + 1], RD[1][val - ADD][c - a + 1]);
  247.                 tree[q] = Node(RD[0][val - ADD][b - d + 1], RD[1][val - ADD][b - d + 1]);
  248.             }
  249.             lazy[idx] = 0;
  250.         }
  251.     }
  252.     inline void build_tree(int idx, int a, int b){
  253.         lazy[idx] = 0;
  254.         if (a == b){
  255.             tree[idx].H[0] = tree[idx].H[1] = ar[a];
  256.             return;
  257.         }
  258.         int p = (idx << 1), q = p + 1;
  259.         int c = (a + b) >> 1, d = c + 1;
  260.         build_tree(p, a, c);
  261.         build_tree(q, d, b);
  262.         tree[idx].H[0] = ((tree[p].H[0] * (long long) P[0][b - d + 1]) + tree[q].H[0]) % MOD[0];
  263.         tree[idx].H[1] = ((tree[p].H[1] * (long long) P[1][b - d + 1]) + tree[q].H[1]) % MOD[1];
  264.     }
  265.     inline void update(int idx, int a, int b, int l, int r, int val){
  266.         if (a == l && b == r){
  267.             lazy[idx] = val;
  268.             tree[idx] = Node(RD[0][val - ADD][b - a + 1], RD[1][val - ADD][b - a + 1]);
  269.             propagate(idx, a, b);
  270.             return;
  271.         }
  272.         propagate(idx, a, b);
  273.         int p = (idx << 1), q = p + 1;
  274.         int c = (a + b) >> 1, d = c + 1;
  275.         if (r <= c) update(p, a, c, l, r, val);
  276.         else if (l >= d) update(q, d, b, l, r, val);
  277.         else{
  278.             update(p, a, c, l, c, val);
  279.             update(q, d, b, d, r, val);
  280.         }
  281.         tree[idx].H[0] = ((tree[p].H[0] * (long long) P[0][b - d + 1]) + tree[q].H[0]) % MOD[0];
  282.         tree[idx].H[1] = ((tree[p].H[1] * (long long) P[1][b - d + 1]) + tree[q].H[1]) % MOD[1];
  283.     }
  284.     inline Node query(int idx, int a, int b, int l, int r){
  285.         propagate(idx, a, b);
  286.         int p = (idx << 1), q = p + 1;
  287.         int c = (a + b) >> 1, d = c + 1;
  288.         if (a == l && b == r) return tree[idx];
  289.         if (r <= c) return query(p, a, c, l, r);
  290.         else if (l >= d) return query(q, d, b, l, r);
  291.         else{
  292.             Node x = query(p, a, c, l, c);
  293.             Node y = query(q, d, b, d, r);
  294.             for (int i = 0; i < 2; i++){
  295.                 x.H[i] = ((P[i][r - d + 1] * (long long) x.H[i]) + y.H[i]) % MOD[i];
  296.             }
  297.             return x;
  298.         }
  299.     }
  300.     /// Note 0-based index used for string update and gethash
  301.     inline void update(int l, int r, char ch){ /// Sets the sub-string in str[l:r] to ch
  302.         update(1, 1, n, ++l, ++r, getval(ch) + ADD);
  303.     }
  304.     inline long long gethash(int l, int r){
  305.         Node h = query(1, 1, n, ++l, ++r);
  306.         return (h.H[0] << 32) | h.H[1];
  307.     }
  308. }
  309.  
  310.  
  311.  
  312. /// Double Hashing
  313. struct simplehash{
  314.     int len;
  315.     long long base, mod;
  316.     vector <int> P, H, R;
  317.     simplehash(){}
  318.     simplehash(const char* str, long long b, long long m){
  319.         base = b, mod = m, len = strlen(str);
  320.         P.resize(len + 3, 1), H.resize(len + 3, 0), R.resize(len + 3, 0);
  321.         for (int i = 1; i <= len; i++) P[i] = (P[i - 1] * base) % mod;
  322.         for (int i = 1; i <= len; i++) H[i] = (H[i - 1] * base + str[i - 1] + 1007) % mod;
  323.         for (int i = len; i >= 1; i--) R[i] = (R[i + 1] * base + str[i - 1] + 1007) % mod;
  324.     }
  325.     inline int range_hash(int l, int r){
  326.         int hashval = H[r + 1] - ((long long)P[r - l + 1] * H[l] % mod);
  327.         return (hashval < 0 ? hashval + mod : hashval);
  328.     }
  329.     inline int reverse_hash(int l, int r){;
  330.         int hashval = R[l + 1] - ((long long)P[r - l + 1] * R[r + 2] % mod);
  331.         return (hashval < 0 ? hashval + mod : hashval);
  332.     }
  333. };
  334. struct stringhash{
  335.     simplehash sh1, sh2;
  336.     stringhash(){}
  337.     stringhash(const char* str){
  338.         sh1 = simplehash(str, 1949313259, 2091573227);
  339.         sh2 = simplehash(str, 1997293877, 2117566807);
  340.     }
  341.     inline long long range_hash(int l, int r){
  342.         return ((long long)sh1.range_hash(l, r) << 32) ^ sh2.range_hash(l, r);
  343.     }
  344.     inline long long reverse_hash(int l, int r){
  345.         return ((long long)sh1.reverse_hash(l, r) << 32) ^ sh2.reverse_hash(l, r);
  346.     }
  347. };
  348.  
  349.  
  350.  
  351. /// Bit string LCS
  352. #include <time.h>
  353. #define MAX 100010
  354. bool flag[MAX];
  355. char A[MAX], B[MAX], S[2][MAX];
  356. int lcs(char* A, char* B){
  357.     int i, j, k, v, n, m, res = 0;
  358.     unsigned long long x, t, q, y, mask[128] = {0};
  359.     memset(flag, 0, sizeof(flag));
  360.     for (n = 0; A[n]; n++) S[0][n] = A[n];
  361.     for (m = 0; B[m]; m++) S[1][m] = B[m];
  362.     for (i = 0; (i * 64) < m; i++){
  363.         memset(mask, 0, sizeof(mask));
  364.         for (k = 0; k < 64 && (i * 64 + k) < m; k++){
  365.             mask[S[1][i * 64 + k]] |= (1ULL << k);
  366.         }
  367.         for (j = 0, x = 0; j < n; j++){
  368.             t = mask[S[0][j]] & ~x;
  369.             x |= t, v = flag[j];
  370.             q = x - (t << 1) - v, y = (q & ~x) | t;
  371.             flag[j] = y >> 63, x &= ~(y << 1);
  372.             if (v) x &= ~1ULL;
  373.         }
  374.         res += __builtin_popcountll(x);
  375.     }
  376.     return res;
  377. }
  378. int main(){
  379.     int i, j, k, n, m;
  380.     n = MAX - 10, m = MAX - 10;
  381.     for (i = 0; i < n; i++) A[i] = (rand() % 26) + 'a';
  382.     for (i = 0; i < m; i++) B[i] = (rand() % 26) + 'a';
  383.     A[n] = B[m] = 0;
  384.     clock_t start = clock();
  385.     printf("%d\n", lcs(A, B));
  386.     printf("%0.6f\n", (clock() - start) / (1.0 * CLOCKS_PER_SEC));
  387.     return 0;
  388. }
  389.  
  390.  
  391.  
  392. /// 2D Pattern Matcher
  393. const unsigned long long base = 1995433697ULL;
  394. const unsigned long long fuck = 1000000007ULL;
  395. int n, m, r, c;
  396. char str[2010][2010], pattern[2010][2010];
  397. unsigned long long pattern_hash, P[2010], F[2010], ar[2010];
  398. void Pregenerate(){
  399.     int i, j;
  400.     pattern_hash = 0;
  401.     for (i = 0; i < r; i++){
  402.         unsigned long long res = 0;
  403.         for (j = 0; j < c; j++) res = (res * fuck) + pattern[i][j];
  404.         pattern_hash = (pattern_hash * base) + res;
  405.     }
  406. }
  407. int Solve(){
  408.     int i, j, res = 0;
  409.     unsigned long long x = 0, y;
  410.     for (i = 0; i < r; i++) x = (x * base) + ar[i];
  411.     for (i = 0; i < n; i++){
  412.         if ((i + r) > n) break;
  413.         if (x == pattern_hash) res++;
  414.         y = (x - (P[r - 1] * ar[i]));
  415.         x = (y * base) + ar[i + r];
  416.     }
  417.     return res;
  418. }
  419. int main(){
  420.     int i, j, k, l;
  421.     P[0] = F[0] = 1;
  422.     for (i = 1; i < 2010; i++){
  423.         P[i] = P[i - 1] * base;
  424.         F[i] = F[i - 1] * fuck;
  425.     }
  426.     while (scanf("%d %d %d %d", &r, &c, &n, &m) != EOF){
  427.         for (i = 0; i < r; i++) scanf("%s", pattern[i]);
  428.         for (i = 0; i < n; i++) scanf("%s", str[i]);
  429.         int res = 0;
  430.         Pregenerate();
  431.         for (i = 0; i < n; i++){
  432.             unsigned long long res = 0;
  433.             for (j = 0; j < c; j++) res = (res * fuck) + str[i][j];
  434.             ar[i] = res;
  435.         }
  436.         for (j = 0; j < m; j++){
  437.             if ((j + c) > m) break;
  438.             res += Solve();
  439.             for (i = 0; i < n; i++){
  440.                 unsigned long long x = ar[i];
  441.                 x = x - (F[c - 1] * str[i][j]);
  442.                 ar[i] = (x * fuck) + str[i][j + c];
  443.             }
  444.         }
  445.         printf("%d\n", res);
  446.     }
  447.     return 0;
  448. }
Advertisement
Add Comment
Please, Sign In to add comment
Public Pastes
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!