Lexicographic rank of a string among all its substrings | C ++ program for the above approach ; Function to find lexicographic rank of string among all its substring ; Length of string ; Traverse the given string and store the indices of each character ; Extract the index ; Store it in the vector ; Traverse the alphaIndex array lesser than the index of first character of given string ; If alphaIndex [ i ] size exceeds 0 ; Traverse over the indices ; Add count of substring equal to n - alphaIndex [ i ] [ j ] ; Store all substrings in a vector str starting with the first character of the given string ; Insert the current character to substring ; Store the substring formed ; Sort the substring in the lexicographical order ; Find the rank of given string ; increase the rank until the given string is same ; If substring is same as the given string ; Add 1 to rank of the given string ; Driver Code ; Given string ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int lexicographicRank ( string s ) { int n = s . length ( ) ; vector < int > alphaIndex [ 26 ] ; for ( int i = 0 ; i < s . length ( ) ; i ++ ) { int x = s [ i ] - ' a ' ; alphaIndex [ x ] . push_back ( i ) ; } int rank = 0 ; for ( int i = 0 ; i < 26 && ' a ' + i < s [ 0 ] ; i ++ ) { if ( alphaIndex [ i ] . size ( ) > 0 ) { for ( int j = 0 ; j < alphaIndex [ i ] . size ( ) ; j ++ ) { rank = rank + ( n - alphaIndex [ i ] [ j ] ) ; } } } vector < string > str ; for ( int i = 0 ; i < alphaIndex [ s [ 0 ] - ' a ' ] . size ( ) ; i ++ ) { string substring ; int j = alphaIndex [ s [ 0 ] - ' a ' ] [ i ] ; for ( ; j < n ; j ++ ) { substring . push_back ( s [ j ] ) ; str . push_back ( substring ) ; } } sort ( str . begin ( ) , str . end ( ) ) ; for ( int i = 0 ; i < str . size ( ) ; i ++ ) { if ( str [ i ] != s ) { rank ++ ; } else { break ; } } return rank + 1 ; } int main ( ) { string str = " enren " ; cout << lexicographicRank ( str ) ; return 0 ; }