UVa 11107 – Life Forms (with Suffix Array)

Problem: UVa 11107 – Life Forms

Brief Description: In this problem, we have to find the longest common substrings which are common to more than N/2 strings, where N is the number of given strings.

Solution: This is a very common application of Suffix Array data structure. I was facing difficulty with concatenating 100s of the strings together as N can be as large as 100. If N is smaller we can use special characters like '!', '@', '#', '$' etc. to concatenate them. But when N is large we can’t have so many distinct special characters.

Now, look, why we need these special characters? Because they have less ASCII values than the alphabetical and numerical characters and by using all separators different we can prevent overlaps between 2 or more strings while calculating LCP (longest common prefix).

What about giving the small values to the separators manually than any alphabetical character? In this problem, the strings are consist of lower-case English letters. We are giving the value of the separator, integers, which are less than or equals to 133 and the alphabetical characters greater than 134 when we are initializing the sparse table. That is the trick.

Code:

#include <bits/stdc++.h>

using namespace std;

const int MAX = 201000;

string text;
int tot_strings;
int strIndx[MAX];

#define LN 21
int suffixRank[MAX+5][LN]; //suffixRank[i][j] stores the sorted position of the substring starting
//at i with length 2^j.that is:
//consider first 2^j chars from i th char of the string.

struct Entry {
    int st; //st->starting position of string
    int r[2]; //r[0]->rank of first part, r[1]->rank of second part
} x[MAX+5];

Entry tmpX[MAX+5];
int c[MAX+5];
const int offset = 135;
void countingSort(int n, int pos)
{
    memset(c, 0, sizeof(c));
    for(int i = 0; i < n; i++) {
        c[x[i].r[pos]+1]++; //+1 to deal with -1
    }
    int prev, sum = 0;
    for(int i = 0; i < MAX; i++) {
        prev = c[i];
        c[i] = sum; //cumulative sum of all elements before c[i]
        sum += prev;
    }
    //now c[i] indicates the first position of x[i] in tmpX
    for(int i = 0; i < n; i++) {
        tmpX[c[x[i].r[pos]+1]] = x[i]; //+1 to deal with -1
        c[x[i].r[pos]+1]++; //+1 to deal with -1
    }
    memcpy(x, tmpX, sizeof(tmpX));
}

void radixSort(int n)
{
    countingSort(n, 1); //sort according to 2nd element
    countingSort(n, 0); //sort according to 1st element
}

int suffixArray[MAX+5];
void fillsuffixRank()
{
    int n = text.size();
    //tricky part
    int cc = 133;
    for(int i = 0; i < n; i++) {
        if(text[i] == '$')
            suffixRank[i][0] = cc--;//giving proper rank to separator characters
        else
            suffixRank[i][0] = text[i]-'a'+offset; //giving rank to characters which age greater than separator ranks
    }

    //now the Suffix Array construct as usual
    for(int j = 1; j < LN; j++) { //at the end of each iteration, rank of each 2^j length substring will found
        for(int i = 0; i < n; i++) { //considering 2^(j-1) length substring,starting at i
            x[i].st = i; //starting position of 2^j length substring
            x[i].r[0] = suffixRank[i][j-1]; //rank of 2^(j-1) lengths substring, starting at i
            int p = i + (1 << (j-1)); //considering 2^(j-1) length substring, starting at p
            if(p < n)
                x[i].r[1] = suffixRank[p][j-1]; //rank of 2^(j-1) lengths substring, starting at p
            else
                x[i].r[1] = -1;
        }
        //considering Entry as a two digit number
        radixSort(n);
        int cnt = 0;
        suffixRank[x[0].st][j] = cnt; //laxicographically smallest 2^j length substring's starting
        for(int i = 1; i < n; i++) {
            if(x[i].r[0] != x[i-1].r[0] || x[i].r[1]!=x[i-1].r[1])
                cnt++;
            suffixRank[x[i].st][j] = cnt;
        }
    }
    for(int i = 0; i < n; i++) //suffixArray[i] contains the starting position of lexicographically ith suffix’s starting index in input text
        suffixArray[suffixRank[i][LN-1]] = i;
}

int lcpf(int a, int b)  //LCP of two suffixes, one starts at a, and another starts at b
{
    int r = 0;
    int n = text.size();
    if(a == b)
        return n-a;
    for(int i = LN-1; i >= 0 && a < n && b < n; i--) {
        if(suffixRank[a][i] == suffixRank[b][i]) {
            r += (1<<i);
            a += (1<<i);
            b += (1<<i);
        }
    }
    return r;
}

int fre[105];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    bool sp = false;
    while(true) {
        cin >> tot_strings;
        if(tot_strings <= 0)
            break;

        if(sp)
            cout << endl;
        sp = true;

        string s;
        cin >> s;
        if(tot_strings == 1) {
            cout << s << endl;
            continue;
        }
        s.push_back('$');
        text += s;
        strIndx[text.size()]++;
        for(int i = 1; i < tot_strings; i++) {
            cin >> s;
            s.push_back('$');
            text += s;
            strIndx[text.size()]++;//start of next
        }
        for(int i = 1; i < MAX; i++) {
            strIndx[i] += strIndx[i-1];//now strIndx[i] stores, text[i] comes from which input string
        }
        fillsuffixRank();

        set<int>ss;
        int half = tot_strings/2;
        int mx = 0;
        for(int i = 0, j = -1; i < text.size(); i++) {
            ss.insert(strIndx[suffixArray[i]]);
            fre[strIndx[suffixArray[i]]]++;
            if(ss.size() > half) {
                j++;
                while(j < i && ss.size() > half) {
                    mx = max(mx, lcpf(suffixArray[j], suffixArray[i]));
                    int p = strIndx[suffixArray[j]];
                    fre[p]--;
                    if(fre[p] == 0)
                        ss.erase(p);
                    j++;
                }
                j--;
            }
        }
        if(mx) {
            memset(fre, 0, sizeof(fre));
            ss.clear();
            unordered_set<string>printed;
            for(int i = 0, j = -1; i < text.size(); i++) {
                ss.insert(strIndx[suffixArray[i]]);
                fre[strIndx[suffixArray[i]]]++;
                if(ss.size() > half) {
                    j++;
                    while(j < i && ss.size() > half) {
                        if(mx == lcpf(suffixArray[j], suffixArray[i])) {
                            string pr = text.substr(suffixArray[i], mx);
                            if(!printed.count(pr)) {
                                cout << pr << endl;
                                printed.insert(pr);
                            }
                        }
                        int p = strIndx[suffixArray[j]];
                        fre[p]--;
                        if(fre[p] == 0)
                            ss.erase(p);
                        j++;
                    }
                    j--;
                }
            }
        } else {
            cout << "?" << endl;
        }
        text.clear();
        memset(fre, 0, sizeof(fre));
        memset(strIndx, 0, sizeof(strIndx));
        memset(suffixRank, 0, sizeof(suffixRank));
    }
    return 0;
}

পয়েন্টার (সি ল্যাংগুয়েজ)

C পড়তে গিয়ে সবচেয়ে যে বিষয়ে বিভ্রান্তিতে পড়তে হয় তা হল Pointer. তাই পয়েন্টার নিয়ে কিছু বলার চেষ্টা………

আমরা জানি, আমরা যত ভেরিয়েবই ব্যবহার করি না কেন তার সবই কম্পিউটার মেমরিতে সেভ হয়, কম্পিউটার মেমরি অনেকগুলো বিট নিয়ে গঠিত। আবার ৮টা বিট নিয়ে ১টা বাইট। বাইট হচ্ছে কম্পিউটার মেমরির ক্ষুদ্রতম ব্যবহারিক একক। তাই প্রতিটা বাইটের একটা করে ঠিকানা থাকে যাকে বলি memory address. আসলে ভেরিয়েবল নাম হচ্ছে মেমরি অ্যাড্রেসে সংরক্ষিত তথ্যের আয়না। আমরা সচরাচর শুধুই ভেরিয়েবল ব্যবহার করি। কিন্তু মাঝে মাঝে সরাসরি মেমরি অ্যাড্রেস নিয়ে কাজ করা লাগে তখনই পয়েন্টারের দরকার হয়।

পয়েন্টার নিজেও ভেরিয়েবল এবং পয়েন্টারও মেমরিতেই থাকে, এর নিজেরও মেমরি অ্যাড্রেস থাকে আবার পয়েন্টার মেমরিতে সংরক্ষিত ডাটার ঠিকানা ধারন করে। তার মানে আমরা ভেরিয়েবল ব্যবহার না করে সরাসরি ঐ ভেরিয়েবল মেমরিতে যেখানে সংরক্ষিত আছে সেখানে গিয়ে কাজ করতে পারি।

সাধারন ভেরিয়েবল ডিক্লিয়ারের সিন্ট্যাক্স হচ্ছে,
int a, b;
double c, d;
পয়েন্টার ভেরিয়েবল ডিক্লিয়ারের সিন্ট্যাক্স হচ্ছে,
int *e, *f;
double *g, *h;
তার মানে হচ্ছে কোন ভেরিয়েবল নামের আগে * দিলেই ঐ ভেরিয়েবল ঐ টাইপের ডাটার মেমরি অ্যাড্রেস ধারনের জন্য প্রস্তুত।
কোন ভেরিয়েবলের মেমরি অ্যাড্রেস পাওয়ার জন্য ঐ ভেরিয়েবল নামের আগে & চিহ্ন দিতে হয়। অর্থাৎ আমদের যদি একটা int টাইপের ভেরিয়েবল a থাকে এবং আমরা a এর মেমরি অ্যাড্রেস জানতে চাই তাহলে লিখতে হবে &a. আর আমরা যদি এই অ্যাড্রেসটা সেভ করতে চাই তাহলে আমাদের int টাইপের পয়েন্টার লাগবে।
যেমনঃ
int a;
int *e;
e = &a;
double d;
double *h;
h = &d;
স্ব স্ব টাইপের ডাটার জন্য স্ব স্ব টাইপের পয়েন্টার ব্যবহার করতে হবে।
আবার কোন পয়েন্টারে যে মেমরি অ্যাড্রেস সেভ করা আছে সেই মেমরি অ্যাড্রেসে কি আছে তা দেখার জন্য বা ব্যবহার করার জন্য * ব্যবহার করা হয়।
যেমনঃ
পূর্বের int *e তে কি আছে তা দেখার জন্য printf(“%d”, *e); আর অন্য কোন ভেরিয়েবল int Iএ সেভ করার জন্য i = *e; অথবা অন্য কোন পয়েন্টার int *vএ সেভ করার জন্য v = e লিখতে হয়।

পয়েন্টার ও অ্যারেঃ
কোন int অ্যারে ara[100] হলে এবং কোন int পয়েন্টার p হলে, যদি লেখা হয়
p = &ara[5]
তাহলে p অ্যারের ৫ম element কে পয়েন্ট করছে বা ৫ম element এর মেমরি অ্যাড্রেস সেভ করছে।
আবার p = ara এবং p = &ara[0] একই কথা। কারন অ্যারের নাম প্রথম element এর মেমরি অ্যাড্রেস ধারন করে।

পয়েন্টারের ++ ও –- :
যদি p = &ara[17] হয় এবং
p++ করলে p, ara[18]র মেমরি অ্যাড্রেস ধারন করবে।
p– করলে p, ara[16]র মেমরি অ্যাড্রেস ধারন করবে।
p+=4 করলে p, ara[21]র মেমরি অ্যাড্রেস ধারন করবে।
p-=2 করলে p, ara[15]র মেমরি অ্যাড্রেস ধারন করবে।
কিন্তু
(*p)++ করলে ara[17]র মান ১ বাড়বে।
(*p)– করলে ara[17]র মান ১ কমবে।

(*p)+=4 করলে ara[17]র মান ৪ বাড়বে।
(*p)-=4 করলে ara[17]র মান ৪ কমবে।

আবার p = &ara[17] ও p2 = &ara[45] হলে
p2-p = 45-17=28 (যা ১৭ থেকে ৪৫ এর আগে পর্যন্ত কতটা element আছে তা জানাচ্ছে)
কিন্তু
p2+p করা যায় না।

Heap ব্যবহার করে Median নির্ণয়

সংক্ষেপে প্রোব্লেম ডিস্ক্রিপশনঃ

একটা একটা করে নম্বর ইনপুট হিসেবে আসতে থাকবে আর প্রতি বার ইনপুটের জন্য আউটপুট হিসেবে দেখাতে হবে শুরু থেকে ইনপুটকৃত ডাটা গুলোর Median কত। Median হলো একটা সর্টেড লিস্টের(or array) মাঝের ডাটা। যদি লিস্টে বেজোড় সংখ্যক ডাটা থাকে তাহলে মাঝের ডাটা আর যদি জোড় সংখ্যক ডাটা থাকে তাহলে মাঝের দুটো ডাটার গড়। সর্টেড লিস্ট হল এমন একটি লিস্ট যেখানে ডাটা গুলো ছোট থেকে বড় বা বড় থেকে ছোট আকারে সাজানো থাকে।

প্রথমেই একটি উদাহরণের মাধ্যমে বোঝার চেষ্টা করা যাকঃ

ইনপুটঃ ইনপুট হিসেবে একে একে নিচের নম্বর গুলো আসতে থাকবে…
১, ২, ৫, ৪, ৫, ৮, ৭, ৬, ২, ০, ৩, ১, ৪


ইনপুট ১ (ইনপুট হিসেবে আসলো ১)
লিস্টঃ {১}
সর্টেড লিস্টঃ {}
Median: ১

ইনপুট ২ (ইনপুট হিসেবে আসলো ২লিস্টঃ {১, ২}
সর্টেড লিস্টঃ {,}
Median: (১+২)/২ = ১.৫

ইনপুট ৫ (ইনপুট হিসেবে আসলো ৫)
লিস্টঃ {১, ২, ৫}
সর্টেড লিস্টঃ {১, , ৫}
Median: ২

ইনপুট ৪
লিস্টঃ {১, ২, ৫, ৪}
সর্টেড লিস্টঃ {১, ,, ৫}
Median: (২+৪)/২ = ৩

ইনপুট ৫
লিস্টঃ {১, ২, ৫, ৪, ৫}
সর্টেড লিস্টঃ {১, ২, , ৫, ৫}
Median: ৪

ইনপুট ৮
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮}
সর্টেড লিস্টঃ {১, ২, ,, ৫, ৮}
Median: (৪+৫)/২ = ৪.৫

ইনপুট ৭
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮, ৭}
সর্টেড লিস্টঃ {১, ২, ৪, , ৫, ৭, ৮}
Median: ৫

ইনপুট ৬
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮, ৭, ৬}
সর্টেড লিস্টঃ {১, ২, ৪, ,, ৬, ৭, ৮}
Median: (৫+৫)/২ = ৫

ইনপুট ২
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮, ৭, ৬, ২}
সর্টেড লিস্টঃ {১, ২, ২, ৪, , ৫, ৬, ৭, ৮}
Median: ৫

ইনপুট ০
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮, ৭, ৬, ২, ০}
সর্টেড লিস্টঃ {০, ১, ২, ২, ,, ৫, ৬, ৭, ৮}
Median: (৪+৫)/২ = ৪.৫

ইনপুট ৩
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮, ৭, ৬, ২, ০, ৩}
সর্টেড লিস্টঃ {০, ১, ২, ২, ৩, , ৫, ৫, ৬, ৭, ৮}
Median: ৪

ইনপুট ১
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮, ৭, ৬, ২, ০, ৩, ১}
সর্টেড লিস্টঃ {০, ১, ১, ২, ২, ,, ৫, ৫, ৬, ৭, ৮}
Median: (৩+৪)/২ = ৩.৫

ইনপুট ৪
লিস্টঃ {১, ২, ৫, ৪, ৫, ৮, ৭, ৬, ২, ০, ৩, ১, ৪}
সর্টেড লিস্টঃ {০, ১, ১, ২, ২, ৩, , ৪, ৫, ৫, ৬, ৭, ৮}
Median: ৪

এভাবে যদি n সংখ্যক নম্বর ইনপুট নিয়ে n সংখ্যক আউটপুট দিতে হয় তাহলে প্রতিবার ইনপুট নিয়ে সর্ট করে Median গণনা করতে হবে।


এখানে সর্টেড লিস্টের একটি বৈশিষ্ট খেয়াল করলে Heap ব্যবহার করে সল্ভ করা যায়। উপরের সর্টেড লিস্ট গুলো আর তাদের Median খেয়াল করলে দেখা যায় যে আমরা শুধু মাঝের একটি বা দুইটি সংখ্যা নিয়ে Median বের করছি। আমরা যদি লিস্টটাকে “প্রায় সমান” ভাগে ভাগ করি তাহলে লিস্টের প্রথমার্ধে যে সংখ্যা গুলো থাকে তাদের মধ্যে সবচেয়ে বড় সংখ্যাটা লিস্টের প্রথমার্ধের শেষে থাকে। আর লিস্টের দ্বিতীয়ার্ধে যে সংখ্যা গুলো থাকে তাদের মধ্যে সবচেয়ে ছোট সংখ্যাটা লিস্টের দ্বিতীয়ার্ধের প্রথমে থাকে। পুরো লিস্টে যদি “জোড় সংখ্যক” সংখ্যা থাকে তাহলে Median হবে লিস্টের প্রথমার্ধের শেষ সংখ্যা ও লিস্টের দ্বিতীয়ার্ধের প্রথম সংখ্যার গড়। অথবা পুরো লিস্টে যদি বেজোড় সংখ্যক সংখ্যা থাকে এবং যদি প্রথমার্ধে বেশি সংখ্যা থাকে তাহলে “প্রথমার্ধের শেষ” সংখ্যাটিই হবে Median অথবা যদি দ্বিতীয়ার্ধে বেশি সংখ্যা থাকে তাহলে “দ্বিতীয়ার্ধের প্রথম” সংখ্যাটিই হবে Median.

এতক্ষন যা বলা হল তাতে আশা করি এটুকু পরিস্কার যে লিস্টের প্রথমার্ধকে Max-Heap আর দ্বিতীয়ার্ধকে Min-Heap হিসেবে রেখে Median বের করা যাবে।

এই কাজ করার জন্য ইনপুটের প্রথম দুটি সংখ্যা নিয়ে ছোট সংখ্যাটিকে Max-Heapএ আর বড় সংখ্যাটিকে Min-Heapএ পুশ(push operation) করতে হবে। এর পর যে সংখ্যা গুলো ইনপুট হিসেবে আসবে তাদের প্রত্যেকটিকে Max-Heap এর রুটের সাথে তুলনা করতে হবে, যদি সংখ্যাটি ছোট হয় তাহলে Max-Heap এ পুশ করতে হবে আর বড় বা সমান হলে Min-Heap এ পুশ করতে হবে।

এই কাজ গুলো করার পর একটি বিষয় খেয়াল রাখতে হবে, সেটি হলঃ একটি Heapএ অন্যটির চেয়ে ১ টির বেশি সংখ্যা থাকলে Heap দুটি ব্যালেন্স করতে হবে অর্থাৎ একটি heapএ মোট সংখ্যা(Heap size) ও অন্য Heap এ মোট সংখ্যার পার্থক্য ১ এর বেশি হবে না। এটি করার জন্য যে Heap এ বেশি সংখ্যা থাকবে সে Heap থেকে রুটটি পপ(pop operation) করে অন্য Heapএ পুশ করতে হবে।

Median নির্ণয় করার জন্যঃ যদি দুটি Heapএ সমান সংখ্যক সংখ্যা থাকে তাহলে Median হবে তাদের রুটদ্বয়ের গড় আর তা না হলে যে Heapএ বেশি সংখ্যা থাকবে তার রুটটি হবে Median.

কোডঃ
“Introduction to Algorithm” book’s Heap implementation
“Light OJ” Heap implementation