epMAHFUZ: October 2017

Monday, October 23, 2017

Clear Idea of Lazy Propagation (Segment Tree)

Segment Tree শেখার জন্য শাফায়েত ভাইয়ের এই টিউটোরিয়াল বেশ সহজ।

If you know already Segment Tree and Lazy Propagation it will be helpful for you. In the following picture the updating system is described.

Thursday, October 19, 2017

Implementation of Segment Tree

/* Creating a segment tree. Then with the query()
we can easily find the sum of any segment of the tree.
*/

#include<bits/stdc++.h>
using namespace std;
#define mx 100001

#define fi(a, b) for(int i=a; i<=b; i++)
#define fd(a, b) for(int i=a; i>=b; i--)

int n, m, ar[mx], tree[mx*3], ii, jj;

void segmentt(int node, int st, int en){
    if(st==en){
        tree[node]=ar[st];
        return ;
    }
    int left=node*2;
    int right=node*2+1;
    int mid=(st+en)/2;
    segmentt(left, st, mid);
    segmentt(right, mid+1, en);
    tree[node]=tree[left]+tree[right];
}

int query(int node, int st, int en){
    if(ii<=st && jj>=en) return tree[node];  // relevant segment
    else if(ii>en || jj<st) return 0;        // out of the segment
    else{                                    // needs to divide again
        int left=2*node, right=node*2+1, mid=(st+en)/2;
        return (query(left, st, mid) + query(right, mid+1, en));
    }
}

int main(){
    cin>>n;
    fi(1, n)
        cin>>ar[i];
    segmentt(1, 1, n);
    cin>>m;
    fi(1, m){
        cin>>ii>>jj;
        cout<<query(1, 1, n)<<endl;
    }
    return 0;
}

Print Longest Common Substring

/* You are given two string. Find the Largest
Common Substring (not Subsequence).
First, insert all the suffix (suffix of "suffix" are "x",
"ix"......"suffix") of the first string in the "Trie",
then check with the all the second-string-suffix's.
*/

#include<bits/stdc++.h>
using namespace std;

int cnt=1, ans=0, st=0;
string s, ss;

struct node{
    int next[26+1];
}ar[10000];

void new_trie(int cur){
    for(int i=0; i<=26; i++)
        ar[cur].next[i]=-1;
}

void insert(){  // Inserting the first string
    int sz=s.size(), cur=0, x;
    for(int i=0; i<sz; i++){
        x=s[i]-'a';
        if(ar[cur].next[x]==-1){
            ar[cur].next[x]=cnt;
            new_trie(cnt++);
        }
        cur=ar[cur].next[x];
    }
}

void find(int stt){  // Checking with the second string
    int sz=s.size(), cur=0, x, c=0;
    for(int i=0; i<sz; i++){
        x=s[i]-'a';
        if(ar[cur].next[x]==-1)
            break;
        cur=ar[cur].next[x];
        c++;
    }
    if(c>ans){  // when larger counter(c) is found
        st=stt;
        ans=c;
    }
}

int main(){
    int sz;
    new_trie(0);
    cin>>ss;   // First String
    sz=ss.size();
    for(int i=1; i<=sz; i++){
        s="";
        for(int ii=sz-i; ii<sz; ii++)
            s+=ss[ii];
        insert();
    }

    cin>>ss;  // Second String
    sz=ss.size();
    for(int i=1; i<=sz; i++){
        s="";
        for(int ii=sz-i; ii<sz; ii++)
            s=s+ss[ii];
        find(sz-i);
    }
    for(int i=st, cc=1; cc<=ans; i++, cc++)
        cout<<ss[i];
    return 0;
}