0

Algorithm:-

  1. s --> given string whose suffix strings are to be sorted (let s = 'ababba')

  2. add a special symbol '$' at end of 's', '$' is smallest character. (s = 'ababba$'

  3. Represent all suffix strings by integers representing the beginning index of suffix string. (suffixStrings = [6, 5, 4, 3, 2, 1, 0])

  4. Then, compare 1st character of all suffixes, and partition them based on their 1st character. (Partitions = [(6), (0, 2, 5), (4, 3, 1)], representing --> [('$'), ('ababba$', 'abba$', 'a$'), ('ba$', 'bba$', 'babba$')]

  5. if any partition containes a single string, print it, since it is smallest string among remaining suffixes

  6. Partition the remaing partitions based on 2nd character.

  7. Continue this process 3rd, 4th and so on characters, until all partitions remain with only one string.

Here is the code.

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

void sortSuffixes(vector<int> &suffixStrings, int c, const string &s) 
{
    vector< vector<int> > temp;
    int n = suffixStrings.size(); //O(1)

    map<char, vector<int> > mmap;
    for(int i=0;i<n;i++) // O(n)
    {
        mmap[s[suffixStrings[i] + c]].push_back(suffixStrings[i]);
    }

    map<char, vector<int> > :: iterator it = mmap.begin();
    while(it != mmap.end())
    {
        if((it->second).size() == 1)
        {
            cout << (it->second)[0]<<" "; 
        }
        else
        {
            sortSuffixes(it->second, c+1, s);
        }
        it++;
    }
}

int main()
{
    string s;
    cin>>s;

    s = s + '$';
    vector<int> suffixStrings;
    int n = s.length();
    for(int i = n-1; i >= 0; i--) // O(n)
    {
        suffixStrings.push_back(i);
    }

    sortSuffixes(suffixStrings, 0, s);
    return 0;
}

How to calculate it's time complexity? I feel it's O(length of given string)

user4581301
  • 33,082
  • 7
  • 33
  • 54
  • How to calculate it's time complexity? I feel it's O(length of given string) –  Jul 07 '20 at 23:09
  • ahh, i think i got it. It's worst case time complexity is O(n^2). n --> length of given string. Worst case occurs with a string containing all same characters –  Jul 07 '20 at 23:22
  • Normally I'd suggest adding in an `int count = 0` to count all the calls to `sortSuffixes` and test your theory, but the combination of `#include ` and `using namespace std;` [makes a bit of a mess of that](https://godbolt.org/). – user4581301 Jul 07 '20 at 23:26
  • @user4581301 why? does including bits/stdc++.h and std namespace together does anything dangerous? –  Jul 16 '20 at 14:17
  • Link went stale. Bummer. C++17 added std::count` If you make a variable named `count` in the wrong scope it will collide with `std::count`. Instant compiler error. See [Why is “using namespace std;” considered bad practice?](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice) for more details. `#include ` makes it worse by bringing in tens of thousands of additional unnecessary identifiers to collide with. – user4581301 Jul 16 '20 at 15:15

0 Answers0