www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Sorting Assosiative Arrays and Finding Largest Common Substring

reply helxi <brucewayneshit gmail.com> writes:
I was looking for ways to find the largest common substring 
between two given substrings and have learnt
1. .length is of type ulong
2. writing string[int] will not give me a sorted array
3. ulong cannot be sorted by sorted

What's the trick to sort the associative array by their keys?

Code snippet:
....

import std.stdio;

//find the largest substring of the two strings
void main(string[] args){

     string str1 = args[1];
     string str2 = args[2];

     string[ulong] commons;

     //is a char from str1[n] == str2[n]?
     //is the char from str1[n+1] == str2[n+1]?

     for (int i = 0; i < str1.length; i++){
         for (int j = 0; j < str2.length; j++){
             if (str2[j] == str1[i]){
                 string current = ""~str1[i];
                 for (int a = 1; (a+i < str1.length && a+j < 
str2.length); a++){
                     if(str2[a+j] == str1[a+i]){
                         current ~= str1[a+i];
                     }
                 }
                 commons[current.length] = current;
             }
         }
     }
     writeln(commons); //[4:"asdf", 2:"df", 1:"f", 3:"sdf"]
     //writeln(commons[commons.keys.max]); <-won't work, no max 
for ulong[]
     writeln(commons[commons.keys[0]]); //asdf
     //but can't guarantee the largest value is the first key
}

---
$./main asdf asdfasdfc
[4:"asdf", 2:"df", 1:"f", 3:"sdf"]
Mar 16
next sibling parent thedeemon <dlang thedeemon.com> writes:
On Thursday, 16 March 2017 at 16:02:13 UTC, helxi wrote:
 I was looking for ways to find the largest common substring 
 between two given substrings and have learnt
 1. .length is of type ulong
Only when compiling to 64 bits. On 32-bit target it's different.
 2. writing string[int] will not give me a sorted array
Sure, it's just a hash table, its key type may not even have any ordering, not be comparable.
 What's the trick to sort the associative array by their keys?
If you need the max key value you can just write auto k = commons.byKey.maxElement; so that commons[k] will give you your longest string. (byKey returns a range of keys, maxElement is a function from std.algorithm) You can use .keys property to get an array of keys of associative array so you can sort them if you need. Btw in your case you don't need an array if you're really interested in longest substring, just have a single string variable and update it when current candidate is longer.
Mar 16
prev sibling parent XavierAP <n3minis-git yahoo.es> writes:
On Thursday, 16 March 2017 at 16:02:13 UTC, helxi wrote:
 
 1. .length is of type ulong
Either use auto or if needed size_t. As Thedeemon says this is an alias of ulong on 64-bit and uint on 32. https://dlang.org/spec/hash-map.html
Mar 16