Color Update

template 
struct ColorUpdate {
public:
    struct Range {
        Range(T _l = 0) : l(_l) {}
        Range(T _l, T _r, Info _v) : l(_l), r(_r), v(_v) { }
        T l, r;
        Info v;

        bool operator < (const Range &b) const { return l < b.l; }
    };

    std::vector erase(T l, T r) {
        std::vector ans;
        if(l > r) return ans;
        auto it = ranges.lower_bound(l);
        if(it != ranges.begin()) {
            it--;
            if(it->r > l) {
                auto cur = *it;
                ranges.erase(it);
                ranges.insert(Range(cur.l, l, cur.v));
                ranges.insert(Range(l, cur.r, cur.v));
            }
        }
        it = ranges.lower_bound(r);
        if(it != ranges.begin()) {
            it--;
            if(it->r > r) {
                auto cur = *it;
                ranges.erase(it);
                ranges.insert(Range(cur.l, r, cur.v));
                ranges.insert(Range(r, cur.r, cur.v));
            }
        }
        for(it = ranges.lower_bound(l); it != ranges.end() && it->l < r; it++) {
            ans.push_back(*it);
        }
        ranges.erase(ranges.lower_bound(l), ranges.lower_bound(r));
        return ans;
    }

    std::vector upd(T l, T r, Info v) {
        r++; // To make range inclusive
        auto ans = erase(l, r);
        ranges.insert(Range(l, r, v));
        return ans;
    }

    bool exists(T x) {
        auto it = ranges.upper_bound(x);
        if(it == ranges.begin()) return false;
        it--;
        return it->l <= x && x < it->r;
    }
    std::set ranges;
};

ColorUpdate base;
map table;

void updateFrequency(vector::Range> v){
    for(auto x : v){
        table[x.v] -= x.r - x.l; // not + 1 because R is not inclusive
    }
}

/*
    {1,1,4,6,7,7,7,10}
    vector = {
        {0, 2, 1},
        {2, 3, 4},
        {3, 4, 6},
        {4, 7, 7},
        {7, 8, 10},
    }

*/

void solve(){
    
    int n = 10, L = 4, R = 7;
    base.upd(0, n - 1, 1); // start all list with 1's
    table[1] = n; // update 1 frequency

    int newColor = 8;
    auto result = base.upd(L, R, newColor);
    updateFrequency(result);
    table[newColor] += R - L + 1; // +1 because R is inclusive here 

}
// Problem : https://www.urionlinejudge.com.br/judge/pt/problems/view/2698

MST

#include 

#define N 200005
using namespace std;

struct Edge {
    int u, v, weight;
    Edge(int uu, int vv, int ww): u(uu), v(vv), weight(ww) {};
};

int p[N];
int s[N];

int find(int a) {
    if (p[a] == a) return a;
    return p[a] = find(p[a]);
}
    
void join(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (s[a] < s[b]) swap(a, b);
        p[b] = a;
        s[a] += s[b];
    }
}

vector mst(vector edges, int n){

    vector result;
    n++, cost = 0;

    for(int i = 0; i < N; i++)p[i] = i, s[i] = 1;

    sort(edges.begin(), edges.end(), [](const Edge &A, const Edge &B  ){
        return A.weight < B.weight;
    });

    for (Edge e : edges) {
        if (find(e.u) != find(e.v)) {
            cost += e.weight;
            result.push_back(e);
            table[{e.u, e.v}] = true;
            join(e.u, e.v);
        }
    }
    
    return result;
}

int main(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector edges;

    for(int i = 0; i < m; i++){
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        edges.push_back(Edge(a, b, w));
    }

    vector result = mst(edges, n);
}
// problem : https://www.urionlinejudge.com.br/judge/pt/problems/view/2703

LCA

#include < bits/stdc++.h >
#define ii pair< int,int >
#define ff first
#define ss second
#define pb push_back
#define vi vector< int >
#define ll long long    
#define all(x) (x).begin(), (x).end()
#define allr(x) (x).rbegin(), (x).rend()
#define vll vector< long long >
#define inf (int) 2e9
#define infll (long long) 2e18
#define endl '\n'

using namespace std;
    
struct Edge {
    int u, v, weight;
    Edge(int uu, int vv, int ww): u(uu), v(vv), weight(ww) {};
};
    
class LCA{
    
public:
    
    int n, logN;
    
    bool builded;
    
    vector< vector< int > > dp;
    vector< vector< pair > > graph;
    vector< int > level;
    vector< vector< int >  > maxEdge;
    
    void populateDP(int u, int nodeParent){
        if(~nodeParent) level[u] = level[nodeParent] + 1;
        dp[u][0] = nodeParent;
        maxEdge[u][0] = edgeCost[{u, nodeParent}];
        for(auto v : graph[u]) if(v.first != nodeParent) populateDP(v.first, u);
    }
    
    pair walk(int u, int d){
        int ans = 0;
        while(d){
            int jump = (int)log2(d);
            ans = max(ans, maxEdge[u][jump]);
            u = dp[u][jump];
            d -= (1 << jump);
        }
        return {u, ans};
    }
    
    void build(){
        builded = true;
        populateDP(1, -1);
        for(int col = 1; col < logN; col++){
            for(int i = 2; i <= n; i++){
                dp[i][col] = dp[i][col - 1] == -1 ? -1:dp[dp[i][col - 1]][col - 1];
                maxEdge[i][col] = dp[i][col - 1] == -1 ? -1:max(maxEdge[i][col - 1], maxEdge[dp[i][col - 1]][col - 1]);
            }
        }
    }
    
    LCA(int _n){
        n = _n;
        builded = false;
        logN = (int)log2(n * 2);
        level = vector< int >(n * 2, 0);
        graph = vector< vector< pair > >(n * 2);
        dp = vector< vector< int > >(n * 2, vector< int >(logN * 2, -1));
        maxEdge =  vector< vector< int > >(n * 2, vector< int >(logN * 2, -1));
    }


    void insert(Edge e){
        graph[e.u].push_back({e.v, e.weight});
        graph[e.v].push_back({e.u, e.weight});
    }
    
    int getLCA(int u, int v){
        if(!builded) build();
        int du = level[u], dv = level[v];
        if(du < dv) return getLCA(v, u);
    
        int diff = du - dv;
        u = walk(u, diff).first;
        
        if(u == v) return u;
    
        for(int i = logN; i >= 0; i--) if(dp[u][i] != -1 and dp[u][i] != dp[v][i]) u = dp[u][i], v = dp[v][i];
        
        return dp[u][0];
    }

    int getMax(int u, int v){
        if(!builded) build();

        int du = level[u], dv = level[v];
        if(du < dv) return getMax(v, u);

        int ans = 0;
        int diff = du - dv;
        tie(u, ans) = walk(u, diff);
        
        if(u == v)  return ans;

        for(int i = logN; i >= 0; i--) 
            if(dp[u][i] != -1 and dp[u][i] != dp[v][i]) 
                ans = max(ans, maxEdge[u][i]), ans = max(ans, maxEdge[v][i]), u = dp[u][i], v = dp[v][i];
            
        return max(ans, max(maxEdge[u][0], maxEdge[v][0]));
    }
    
    int dist(int u, int v){ // Only if edge = 1
        return level[u] + level[v] - 2 * level[getLCA(u, v)];
    }
};
    
void solve(){
    int n;
    scanf("%d", &n);
    
    LCA l(n);
    
    for(int i = 1; i < n; i++){
        int a, b, w;
        scanf("%d %d %d", &a, &b, &w);
        l.insert(Edge(a, b, w));
    }

    auto lca = l.getLCA(a, b);
    auto dist = l.dist(a, b);
    auto maxEdge = l.getMax(a, b);
}

Trie

class Trie {
private:
    Node *main;
    
    class Node {
    public:
        vector< Node* > children;
        bool isLeaf;

        Node(){
            children.resize(26,NULL);
            isLeaf = false;
        }
    };
    
public:
    
    Trie() {
        main = new Node();
    }
    
    Node* walk(string word){
        Node *root = main;
        for(auto letter : word){
            int indexLetter = letter - 'a';
            if(!root->children[indexLetter])
                return NULL;
            root = root->children[indexLetter]; 
        }
        return root;
    }
    
    void insert(string word) {
        Node *root = main;
        for(auto letter : word){
            int indexLetter = letter - 'a';
            if(!root->children[indexLetter])
                root->children[indexLetter] = new Node();
            root = root->children[indexLetter]; 
        }
        root->isLeaf = true;
    }
    
    bool search(string word) {
        Node *node = walk(word);
        return (node != NULL and node->isLeaf);
    }
    
    bool startsWith(string prefix) {
        Node *node = walk(prefix);
        return node != NULL;
    }
};

int main(){

    Trie *root = new Trie();

    root->insert("apple");
    cout << (root->search("apple") ? "apple TRUE":"apple FALSE") << endl;
    cout << (root->search("app") ? "app TRUE":"app FALSE") << endl;
    cout << (root->startsWith("app") ? "app starts TRUE":"app starts FALSE") << endl;
    return 0;
}

Area from Histogram

int calc(stack< int > &s, vector< int > hist, int i){
  int top = s.top(); s.pop();
  int curr_area = hist[top] * (s.empty() ? i : i - s.top() - 1); 
  return curr_area;
}

int getMaxAreaFromHistogram(vector< int > hist){ 
    stack< int > s;
  int n = hist.size(), ans = 0, i = 0;
    while (i < n) { 
        if (s.empty() || hist[s.top()] <= hist[i]) s.push(i++); 
        else ans = max(ans, calc(s, hist, i));
    } 
    while (!s.empty()) ans = max(ans, calc(s, hist, i));
    return ans; 
}

Prefix Sum 2D

vector< vector > buildPsum(int n, int m, vector< vector< int > >& mat){
    vector< vector > psum(n + 1, vector(m + 1, 0));
    psum[1][1] = mat[0][0];

    for(int i = 2; i <= m; i++) psum[1][i] = psum[1][i - 1] + mat[0][i - 1];
    for(int i = 2; i <= n; i++) psum[i][1] = psum[i - 1][1] + mat[i - 1][0];
    
    for(int i = 2; i <= n; i++)
        for(int j = 2; j <= m; j++)
            psum[i][j] = psum[i - 1][j] + psum[i][j - 1] - psum[i - 1][j - 1] + mat[i - 1][j - 1];
    
    return psum;
    
}

int calcArea(int i, int j, int width, int high, vector< vector< int > > &psum){
    if(i - high < 0 or j - width < 0) return -1;
    return psum[i][j] - psum[i - high][j] - psum[i][j - width] + psum[i - high][j - width];
}

DSU

int p[N];
int s[N];

int find(int a) {
    if (p[a] == a) return a;
    return p[a] = find(p[a]);
}

void join(int a, int b) {
    a = find(a);
    b = find(b);
    if (a != b) {
        if (s[a] < s[b]) swap(a, b);
        p[b] = a;
        s[a] += s[b];
    }
}

int main(){
    for(int i = 0; i < N; i++)p[i] = i, s[i] = 1;
}

Ordered Set

#include < bits/stdc++.h >
#include < ext/pb_ds/assoc_container.hpp >
#include < ext/pb_ds/tree_policy.hpp >
#include < ext/pb_ds/detail/standard_policies.hpp >

using namespace std;
using namespace __gnu_pbds; // or pb_ds;
template< typename T, typename B = null_type >
using oset = tree< T, B, less< T >, rb_tree_tag, tree_order_statistics_node_update >;

int main(){
    oset< int > ost;
    ost.insert(1);
    ost.insert(2);
    ost.insert(4);
    ost.insert(8);
    ost.insert(16);

    // returns an iterator to the k-th largest element (counting from zero)
    cout << *ost.find_by_order(1) << endl; // 2
    cout << *ost.find_by_order(2) << endl; // 4
    cout << *ost.find_by_order(4) << endl; // 16
    cout << (end(ost)==ost.find_by_order(6)) << endl; // true

    // number of items in a set that are strictly smaller than our item
    cout << ost.order_of_key(-5) << endl;  // 0
    cout << ost.order_of_key(1) << endl;   // 0
    cout << ost.order_of_key(3) << endl;   // 2
    cout << ost.order_of_key(4) << endl;   // 2
    cout << ost.order_of_key(400) << endl; // 5
}

Geometry

typedef struct {    
  long long x,y;
}Point;
  
long long get_line_dist(Point p1, Point p2){
  long long dx = p1.x - p2.x;
  long long dy = p1.y - p2.y;
  return ((dx * dx) + (dy * dy));
}
  
class Rect{
  
  public:
  
    Point b, t;
  
    Rect(int bx, int by, int tx, int ty){
      b.x = bx;
      b.y = by;
      t.x = tx;
      t.y = ty;
    }
  
    Rect(){
      b.x = b.y = t.x = t.y = 0;
    }
  
    bool check_area(){
      if( (t.x - b.x < 0) or (t.y - b.y) < 0)
        return false;
      return true;
    }
  
    long long area(){
        if(!check_area()) return 0;
        return ((t.y - b.y) * (t.x - b.x));
    }
  
    Rect intersect(Rect r){
      Rect inter;
      inter.t.x = min(t.x, r.t.x);
      inter.b.x = max(b.x, r.b.x);
      inter.t.y = min(t.y, r.t.y);
      inter.b.y = max(b.y, r.b.y);
      return inter;
    }
  
};

int main(){
  int n,m;
  scanf("%d %d", &n, &m);
  
  Point line[n];

  for(int i = 0; i < n; i++)
    scanf("%d %d", &line[i].x, &line[i].y);

  for(int i = 0; i < n; i++)
    for(int j = i+1; j < n; j++)
      cout << "Dist de " << i << " - " << j << " = " << sqrt(get_line_dist(line[i],line[j])) << endl; 
    
  Rect rec[m];

  for(int i = 0; i < m; i++)
    scanf("%d %d %d %d",&rec[i].b.x, &rec[i].b.y, &rec[i].t.x, &rec[i].t.y );
  
  Rect area;

  area = rec[0];
  
  for(int i = 0; i < m; i++)
    area = area.intersect(rec[i]);;

  if(area.check_area())
    // Existe intercessão de todos os retangulos
  return 0;
}
  

Segment Tree

class SegTree{

  vector< int > st;
  int n;
  
  void upd(int p, int nodeL, int nodeR, int queryL, int queryR, int v){
  
    if(queryR <  nodeL or  queryL >  nodeR) return;
    if(queryL <= nodeL and queryR >= nodeR){
      st[p] = v;
      return;
    }
  
    int mid = (nodeL + nodeR) / 2;
  
    upd(2*p,   nodeL, mid,   queryL, queryR, v);
    upd(2*p+1, mid+1, nodeR, queryL, queryR, v);
  
    st[p] = max(st[2*p], st[2*p+1]);
  }
  
  int qry(int p, int nodeL, int nodeR, int queryL, int queryR){
  
    if(queryR <  nodeL or  queryL >  nodeR) return 0;
    if(queryL <= nodeL and queryR >= nodeR) return st[p];
  
    int mid = (nodeL + nodeR) / 2;
  
    return max(qry(2*p, nodeL, mid, queryL, queryR), qry(2*p+1, mid+1, nodeR, queryL, queryR));
  }
  
public:
  
  SegTree(int sz){
    n = sz;
    st.assign(5*(n + 1), 0);
  }
  
  int qry(int i, int j){
    return qry(1, 1, n, i, j);
  }
  
  void upd(int i, int j, int v){
    upd(1, 1, n, i, j, v);
  }
  
};

Dijkstra

vector< pair < int,int > > dist(N, {INT_MAX, - 1});
vector< pair < int,int > > graph[N];

void dijkstra(int start){
    priority_queue< pair < int,int >, vector < pair < int,int > >, greater< pair < int,int > > > pq;
    
    dist[start] = {0, -1};
    pq.push({0, start});

    while(!pq.empty()){
        auto currPai = pq.top(); pq.pop();
        int distPai = currPai.first;
        int pai = currPai.second;

        for(auto currFilho: graph[currPai.second]){
            int distPaiFilho = currFilho.second;
            int filho = currFilho.first;

            if(distPai + distPaiFilho < dist[filho].first){
                dist[filho] = {distPai + distPaiFilho, pai};
                pq.push({dist[filho].first, filho});
            }
        }
    }
}

void printCaminho(int x){
    while(x != -1){
        cout << x << " ";
        x = dist[x].second;
    }
    cout << endl;
}

BFS

void bfs(int u){
  queue< int > q;
  dist[u] = 0;
  q.push(u);
  vector< bool > visit(N,false);
  visit[u] = true;
  while(!q.empty()){
    int u = q.front();
    q.pop();
    for(int i = 0 ; i < grafo[u].size(); ++i){
      int v = grafo[u][i];
      if(!visit[v]){
        q.push(v);
        dist[v] = dist[u]+1; 
        visit[v] = true;
      }
    }
  }
}

Binary Search

bool PesquisaBinaria ( int k[], int who , int n){
  int inf,sup,meio;
  inf=0;
  sup=n-1;
  while (inf<=sup)
  {
    meio=(inf+sup)/2;
    if (who==k[meio])
         return true;
    else if (who< k[meio])
         sup=meio-1;
    else
         inf=meio+1;
  }
  return false;  
}

bool IterativeBinaryS(int v[], int x , int n){
  int L = 0, R = n-1;
  bool ans = false;
  for(int i = 0 ; i < 100; i++){
    int mid = (L+R)/2;
    if(v[mid] == x) return true;
    else if(v[mid] > x) R = mid-1;
    else L = mid + 1;
  }
  return false;
}

int main(){
  int x,n;
  printf("Tamanho do vetor: ");
  cin >> n;
  int v[n];
  printf("Digite os valores do vetor\n");
  for(int i = 0; i < n ; i++) scanf("%d", v+i);
  printf("Qual numero deseja buscar?\n");
  scanf("%d", &x);
  printf("%s\n", IterativeBinaryS(v,x,n) ? "Achou":"Nao achou");
  printf("%s\n", PesquisaBinaria(v,x,n) ? "Achou":"Nao achou");
}  

Coin Change Algorithm

int coin(int troco, vector< int > moedas){
  vector< int > ans(troco+1,1e9+7);
  ans[0] = 0;
  for(int i = 1 ; i <= troco; i++){
    for(int j = 0 ; j < moedas.size(); j++){
      if(i < moedas[j]) break;
      ans[i] = min(ans[i],1+ans[i - moedas[j]]);
    }
  }
  return ans[troco];
}

Edit Distance

double st[MAX_M][MAX_N];
double c_i = 2.5, c_r = 0.5, c_s = 1;

double edit(const string& s, const string& r)
{
    int m = s.size();
    int n = r.size();

    for (int i = 0; i <= m; ++i)
        st[i][0] = i*c_r;

    for (int j = 1; j <= n; ++j)
        st[0][j] = j*c_i;

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
        {
            double insertion = st[i][j - 1] + c_i;
            double deletion = st[i - 1][j] + c_r;
            double change = st[i - 1][j - 1] + c_s * (s[i - 1] == r[j - 1] ? 0 : 1);
            st[i][j] = min(insertion, deletion);
            st[i][j] = min(st[i][j], change);
        }

    return st[m][n];
}

Fast Prime

Common algorithm

bool isPrime(long long int n){
    int i;

    if(n==2)
        return true;

    if(n%2==0)
        return false;

    for(i=3;i<=sqrt(n);i+=2)
        if(n%i==0)
            return false;

    return true;
}

Eratóstenes algorithm

vector< bool > prime(N, true);
for(int i = 2; i <= sqrt(N); ++i){
  if(!prime[i]) continue;
  for(int k = i+i; k <= N; k += i) prime[k] = false;
}

Fast Exponential

1:

long long pot(long long x, long long n, long long mod){
  long long ans = 1;
  while(n){
    if(n & 1) ans = (ans * x) % mod;
    x = (x * x) % mod;
    n >>= 1;
  }
  return ans;
}

2:

int sq(int x){
  return x*x;
}

ll pot(ll b, ll n){
  if(n == 0) return 1;
  if(n&1) return b * pot(b,n-1);
  else return sq(pot(b,n/2));
}

Fast Matrix Exponential

typedef struct{
  int m[1006][1006];

}Matriz;

Matriz mul(int n , Matriz* A, Matriz* B){
  int i , j , k;
  Matriz C;
    for(i = 0 ; i < n ; i++)
      for(j = 0 ; j < n ; j++){
        C.m[i][j] = 0;
        for(k = 0 ; k < n ; k++)
          C.m[i][j] = (C.m[i][j] + (A->m[i][k]%13 * B->m[k][j]%13)%13)%13;
      } 
      return C;
}

Matriz power(int n, Matriz base, long long int expo){
  int i , j;
  Matriz resp;

  for(i = 0 ; i < n ; i++)
    for(j = 0 ; j < n ; j++){
      if( i == j)
        resp.m[i][j] = 1;
      else
         resp.m[i][j] = 0;
    }

  while(expo > 0){
    if( expo%2 == 1)
      resp = mul(n, &resp, &base);
    base = mul(n, &base, &base);
    expo /= 2;
  }
  return resp;  
}
int main(){
  int i , j , n, quantos, l,p;
  long long int expo;
  Matriz base;
  scanf("%d %lld", &n, &expo);
  for(i = 0 ; i < n ; i++) for(j = 0 ; j < n ; j++) scanf("%d", &base.m[i][j]);
  base = power(n , base, expo);    
  scanf("%d", &quantos);
  for(i = 0 ; i < quantos; i++){
    scanf("%d %d", &l, &p);
    l--;
    p--;
    printf("%d\n",base.m[l][p]);
  }
}

Kadane

int ans = 0, temp = 0;
for(int i = 0 ; i < n ; i++){
  temp+=v[i];
  ans = max(ans,temp);
  if(temp < 0) temp = 0;
}
cout << ans << endl;

KMP

vector< int > strong_borders(const string& pat){
    int m = pat.size();
    vector< int > sbord(m);
    int t = -1;
    sbord[0] = 0;

    for (int j = 1; j < m; ++j){ 
        while( (t > -1) and pat[t+1] != pat[j]){
            t = sbord[t]-1;
        }
        if( pat[t+1] == pat[j])
            t++;
       
        sbord[j] = t+1;
    }
    return sbord;
}

void KMP(const string& text, const string& pat){
    int n = text.size()-1;
    int m = pat.size()-1;
    int i = 0, j = 0, occ = 0, k = 0;

    vector< int > bords = strong_borders(pat);

    while (n - k >= m)
    {
        while (j <= m and text[i] == pat[j]){
            ++j;
            ++i;
        }

        if (j > m) cout << k << " ";

        if(j-1 >= 0 and bords[j-1] > 0) k = i - bords[j-1];
   
        else{
            if(i == k) i++;
            k = i;
        }

        if(j > 0) j = bords[j-1];
    }     
}

Knapsack

for(int i = 1; i <= n; i++){
  for(int j = 1; j <= t; j++){
    if(p[i].ff <= j) dp[i][j] = max( p[i].ss + dp[i][j - p[i].ff], dp[i-1][j]);
    else dp[i][j] = dp[i-1][j];
  }
}
cout << dp[n][t] << endl;

Longest Common Subsequence

int st[MAX_M][MAX_N], a[MAX_N], b[MAX_N];
int c_i = 0, c_r = 0, c_s = 1;      // Custos adaptados
char ps[MAX_M][MAX_N];

// Implementação _bottom-up_, O(mn), memória O(mn)
int lcs(const string& s, const string& t)
{
    int m = s.size();
    int n = t.size();

    for (int i = 0; i <= m; ++i)
        st[i][0] = i*c_r;

    for (int j = 1; j <= n; ++j)
        st[0][j] = j*c_i;

    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
        {
            int insertion = st[i][j - 1] + c_i;
            int deletion = st[i - 1][j] + c_r; 
            int change = st[i - 1][j - 1] + c_s * (s[i - 1] == t[j - 1] ? 1 : -INF);
            st[i][j] = max(insertion, deletion);
            st[i][j] = max(st[i][j], change);
        }

    return st[m][n];
}

Longest Palindromic Subsequence

int dp[MAX][MAX];

int main(){ 
  
  string a;
  cin >> a;
  int n = a.size();
  
  for(int i = 0 ; i < n ; i++){
    dp[i][i] = 1;
    if(i < n-1) dp[i][i+1] = a[i] == a[i+1] ? 2:1;  
  }
  
  for(int i = 2 ; i < n ; i++){
    for(int j = 0 ; j < n-i ; j++){
      if(a[j] == a[j+i])dp[j][j+i] = 2+dp[j+1][j+i-1];
      
      else dp[j][j+i] = max(dp[j+1][j+i],dp[j][j+i-1]);
    }
  }
  cout << dp[0][n-1] << endl;
}   

void intercalar (int v[],int aux[],int ini1, int ini2,int fim2){
 
  int in1=ini1,in2=ini2,fim1=in2-1,au=0,i;
    while(in1<=fim1 and in2<=fim2){
     
      if (v[in1] < v[in2])      
          aux[au++] = v[in1++];
      
        else
          aux[au++] = v[in2++];   
    }
    while(in1<=fim1)
      aux[au++] = v[in1++];
     
    while(in2<=fim2) 
      aux[au++] = v[in2++];
    
    for(i=0 ; i < au; i++) 
      v[i+ini1]=aux[i];
}
void mergeSort (int v[], int aux[],int esq, int dir){
  int meio;
    if(esq < dir){
      meio=(esq+dir)/2;
      mergeSort(v,aux,esq,meio);
      mergeSort(v,aux,meio+1,dir);
      intercalar(v,aux,esq,meio+1,dir);  
    }
}

String Period

vector< int > strong_borders(const string& pat){
    int m = pat.size();
    vector< int > sbord(m);
    int t = -1;
    sbord[0] = 0;

    for (int j = 1; j < m; ++j){ 
        while( (t > -1) and pat[t+1] != pat[j]){
            t = sbord[t]-1;
        }
        if( pat[t+1] == pat[j])
            t++;
       
        sbord[j] = t+1;
    }
    return sbord;
}


int period(const string& a){
    string aux = a;
    aux += aux;
    int m = aux.size();
    int ans;
    vector< int > v = strong_borders(aux);
    
    for(int i = 0 ; i < aux.size(); i++)
        if(v[i] >= m/2){            
            ans = i - v[i] + 1;
            return ans;
        }
    
}

Strcut Sort

 
typedef struct {
  char pais[200];
  int ouro, prata,bronze;
}selecao;

int cmp (const void *p1, const void *p2){
  selecao *a = (selecao*)p1;
  selecao *b = (selecao*)p2;

  if ( a->ouro > b->ouro)
    return 1;

  else if(a->ouro < b->ouro)
    return -1;

  else{ 
    if ( a->prata > b->prata)
      return 1;
    else if(a->prata < b->prata)
      return -1;
    else{
      if ( a->bronze > b->bronze)
        return 1;
      else if(a->bronze < b->bronze)
        return -1;
      else
        return strcmp(b->pais,a->pais);
    }
  }
}
int main (){
  int n, i;
    scanf("%d", &n);
      selecao v[n];
        for( i = 0 ; i < n ; i++){
          scanf(" %s %d %d %d", v[i].pais, &v[i].ouro, &v[i].prata, &v[i].bronze);
        }
        qsort(v,n,sizeof(selecao),cmp);
        for( i = n-1 ; i >= 0 ; i--)
        printf("%s %d %d %d\n", v[i].pais, v[i].ouro, v[i].prata, v[i].bronze);          
}

Token

int main (){
    string a;
    getline(cin,a);
    a+=' ';
    stringstream ss(a);
    int cont = 0;
    for(int i = 0 ; i < a.size() ; i++)
        if(a[i] == ' ')
            cont++;
    vector  v(cont);
    int i = 0;
    while (getline(ss, a, ' ')) {
        v[i++] = a;
    }
    for(int i = 0 ; i < cont ; i++)
        cout << v[i] << endl;
}

Z Function

vector< int > z_function(const string &s) {
    int n = s.size();
    vector< int > z(n, 0);
    int L = 0, R = 0;
    for(int i = 1; i < n; i++) {
        if(i <= R) {
            z[i] = min(z[i - L], R - i + 1);
        }
        while(z[i] + i < n && s[z[i] + i] == s[z[i]]) {
            z[i]++;
        }
        if(R < i + z[i] - 1) {
            L = i, R = i + z[i] - 1;
        }
    }
    return z;
}

// cada posição do vetor retornado é a maior subsequencia começado em i
/*   i    - 0 1 2 3 4 5 6 7 8 9
    S    - a b a c a b a b a c
    z[i] - 0 0 1 0 3 0 4 0 1 0
*/

//achar matching perfeito
int main(){
  string s , a;
  cin >> s >> a;
  int x = s.size();
  s += "#";
  s += a;
  int n = s.size();
  vector< int > v(n);
  v = z_function(s);
  int ans = 0;
  for(int i = x; i < n ; i++) if(v[i] == x) ans++;
  cout << ans << endl;
  
}