Lexicographic rank of a string among all its substrings | Function to find lexicographic rank of 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 strr starting with the first character of the given string ; Insert the current character to substring ; Store the subformed ; Sort the substring in the lexicographical order ; Find the rank of given string ; Increase the rank until the given is same ; If substring is same as the given string ; Add 1 to rank of the given string ; Driver Code ; Given string ; Function call
def lexicographicRank ( s ) : NEW_LINE INDENT n = len ( s ) NEW_LINE alphaIndex = [ [ ] for i in range ( 26 ) ] NEW_LINE for i in range ( len ( s ) ) : NEW_LINE INDENT x = ord ( s [ i ] ) - ord ( ' a ' ) NEW_LINE alphaIndex [ x ] . append ( i ) NEW_LINE DEDENT rank = - 1 NEW_LINE for i in range ( 26 ) : NEW_LINE INDENT if ord ( ' a ' ) + i >= ord ( s [ 0 ] ) : NEW_LINE INDENT break NEW_LINE DEDENT if len ( alphaIndex [ i ] ) > 0 : NEW_LINE INDENT for j in range ( len ( alphaIndex [ i ] ) ) : NEW_LINE INDENT rank = rank + ( n - alphaIndex [ i ] [ j ] ) NEW_LINE DEDENT DEDENT DEDENT strr = [ ] NEW_LINE for i in range ( len ( alphaIndex [ ord ( s [ 0 ] ) - ord ( ' a ' ) ] ) ) : NEW_LINE INDENT substring = [ ] NEW_LINE jj = alphaIndex [ ord ( s [ 0 ] ) - ord ( ' a ' ) ] [ i ] NEW_LINE for j in range ( jj , n ) : NEW_LINE INDENT substring . append ( s [ j ] ) NEW_LINE strr . append ( substring ) NEW_LINE DEDENT DEDENT strr = sorted ( strr ) NEW_LINE for i in range ( len ( strr ) ) : NEW_LINE INDENT if ( strr [ i ] != s ) : NEW_LINE INDENT rank += 1 NEW_LINE DEDENT else : NEW_LINE INDENT break NEW_LINE DEDENT DEDENT return rank + 1 NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT strr = " enren " NEW_LINE print ( lexicographicRank ( strr ) ) NEW_LINE DEDENT