-3

I needed a JavaScript answer, discovered a C++ solution and converted it. Hopefully others will find this useful.

Mac
  • 1,432
  • 21
  • 27
  • 3
    Do you have a question? – random_user_name Feb 05 '18 at 20:51
  • Seriously? You guys are just a bit too quick on the downvote trigger finger, but be my guest... – Mac Feb 05 '18 at 20:55
  • Huh... looks like the user opened the question to post his own answer for posterity's sake-- not sure if this is an excepted way of using the site or not... – Alexander Nied Feb 05 '18 at 20:55
  • And why not? I searched for the answer I needed and could not find one. Instead of asking others for it, I came up with my own solution based on another forum, posted here for the benefit of others. – Mac Feb 05 '18 at 20:57
  • I did not downvote. I _did_ comment. The downvotes are because the question in the form you posted it was not good per SO guidelines - it showed no effort, and has a link-only reference (which is frowned upon). Posting a question and then answering it yourself _*is*_ an acceptable practice to answer @AlexanderNied comment. – random_user_name Feb 05 '18 at 21:10
  • @cale_b: Nothing wrong with your comment, but my question wasn't more than 5 minutes old, in it's initial format, before the downvotes poured in... while I was pasting in and checking over my answer! Now, an hour later, with the question acceptably rephrased (and answered), the downvotes stick. These DVs will likely prevent my post seeing the light of day... all because people couldn't wait a few minutes. Downvoters: if it's so important to quickly DV, why not circle back to see if what you flagged was corrected by the OP afterwards? Isn't that the point? – Mac Feb 05 '18 at 22:29
  • For reference, I didn't downvote either-- nor am I asking my question in a leading way. It seems a bit strange to me, but I have no issue with it as long as it is an accepted usage per the site rules. I'm guessing there's an answer to this in [meta](https://meta.stackoverflow.com) somewhere... – Alexander Nied Feb 05 '18 at 22:32
  • 1
    After a quick search in [Meta](https://meta.stackoverflow.com), it appears to be [perfectly fine to answer your own question](https://meta.stackoverflow.com/questions/250204/can-you-answer-your-own-questions-on-stack-overflow), even in the [Q&A style you used](https://meta.stackoverflow.com/questions/290038/answer-your-own-question-qa-style). My recommendation would be that, next time you want to post and answer a question in this way, make a note in the question not to downvote, bc you are about to post your own answer. Then just remove that note in an edit after the answer is posted. – Alexander Nied Feb 05 '18 at 22:36
  • @Mac - did you see / find this Q/A in your research? https://stackoverflow.com/questions/3898083/find-longest-repeating-substring-in-javascript-using-regular-expressions – random_user_name Feb 05 '18 at 23:02
  • @cale_b: No sir, I did not. I studiously checked the suggestions that SO provides when a new question is created, but I don't think it was on the list. Had I seen it, I wouldn't have taken the time for all this. Anywho, it's a good answer, but seems slower parsing [large chucks of random data](https://jsperf.com/longest-repeating-substring-first-found-no-overlap), so I'll keep my answer here for whoever may stumble across it. – Mac Feb 07 '18 at 17:34

1 Answers1

1

Converted over from GeeksForGeeks:

function longestRepeatedSubstring( str ) {
    "use strict";

    var n = str.length
        , LCSRe = createArray( n + 1, n + 1 )
        , res = ''
        , res_length = 0
        , index = 0
    ;

    // Setting all to 0
    for( var i = 0; i < n + 1; i++ ) {
         LCSRe[ i ].fill( 0 );
    }

    // building table in bottom-up manner
    for( var i = 1; i <= n; i++ ) {
        for( var j = i + 1; j <= n; j++ ) {

            // (j-i) > LCSRe[i-1][j-1] to remove
            // overlapping
            if(
                str[ i - 1 ] === str[ j - 1 ]
                &&
                LCSRe[ i - 1 ][ j - 1 ] < ( j - i ) 
            ){
                LCSRe[ i ][ j ] = LCSRe[ i - 1 ][ j - 1 ] + 1;

                // updating maximum length of the
                // substring and updating the finishing
                // index of the suffix
                if( LCSRe[ i ][ j ] > res_length ) {
                    res_length = LCSRe[ i ][ j ];
                    index = Math.max( i, index );
                }

            } else {
                LCSRe[ i ][ j ] = 0;
            }
        }
    }

    // If we have non-empty result, then insert all
    // characters from first character to last
    // character of string
    if( res_length > 0 ) {
        for( var i = index - res_length + 1; i <= index; i++ ) {
            res = res.concat( str[ i - 1 ] );
        }
    }

    return res;
}



function createArray( length ) {
    var arr = new Array( length || 0 )
        , i = length
    ;

    if( arguments.length > 1 ) {
        var args = Array.prototype.slice.call( arguments, 1 );
        while( i-- ) {
            arr[ length - 1 - i ] = createArray.apply( this, args );
        }
    }

    return arr;
}

The named function does the job (supported by Matthew Crumley's createArray helper function), but I certainly welcome optimization suggestions. NOTE: As this is converted from C++, I left the original variable names unchanged, as well as most of the original coder's comments.

Some tests:

longestRepeatedSubstring( "SOgeeksforgeeks" );
> geeks

longestRepeatedSubstring( "aab" );
> a

longestRepeatedSubstring( "aabaabaaba" );
> aaba

longestRepeatedSubstring( "aaaaaaaaaaa" );
> aaaaa

longestRepeatedSubstring( "banana" );
> an

To be clear, I missed Ben Doom's contribution before posting. His does the same thing using regex's that this does (using loops). The regex solution handily outperforms the loop solution when checking a "banana," but the loops run significantly faster against a chunk of random data. I won't presume to know everyone's use case, so I'll leave my answer here in the interest of speed.

Mac
  • 1,432
  • 21
  • 27