**Introduction**


I am analyzing the average complexity of an algorithm and it boils down to this question:


**Question**


What is the expected substring length which two randomly generated strings will most likely have?


I found a lot of papers covering this topic on subsequences but couldn't find any for substrings. The difference is that in a subsequence the characters can appear with any space in between as long as they're in the same order but substrings have to be consecutive (i.e. "ABC" has to appear together, "ABxC" doesn't count).


Example: In "ABCED" **and** "ABCXED" the longest substring is "ABC" (length = 3)


**Another way to look at it:**


Example: In "ABCDE" **and** "ABCED" the longest common substring (LCS) is "ABC" (length = 3)


Another (non random) example: "EXXAMPPLEEE" and "XXXAMPPLXXX" would have the longest common substring would be "XAMP" of length = 4.


Assuming that we generate two strings randomly of length $N$ and of alphabet size $q$, measure the length of the longest common substring and repeat this infinitely many times. What is the mean average substring length in function of N, q ?


What would be the expected common substring length to be found in a random string of length $N$ and alphabet $q$


**What I Researched**


My intuition and approximation suggested AVG\_LCS\_LENGTH = $log\_q(N)$
I've read in an unofficial source that it is $2log\_q(N)$ but I couldn't find anything to reference.


**What I'd accept as an answer**


Since I assume that this proof isn't trivial, any reference to a paper proving this and which I could use and reference for my research would be acceptable as an answer or if somebody could write a proof of course.



Mean length of the longest substring (not sequence) of a random string
I don't know if the answer still interest you, anyway:


First of all, you need to define clearly what you mean by longest substring:


-you only look at the longest substring at the beginning of the sequences


-your longest substring can be anywhere but needs to be at the same position in both sequences


-your longest substring can be anywhere


Secondly, you wrote "we generate two strings randomly", I will assume you mean that we are in the iid case.


If it's () or 2() will depend on the definition you choose.


You can see the paper of Arratia and Waterman and the references in the paper: <https://www.sciencedirect.com/science/article/pii/0001870885900039>


If you want results for more general processes (not only iid), the answers will be different and will involve the Renyi entropy. You can see this paper and the references therein:
<https://www.sciencedirect.com/science/article/pii/S000187081930026X>


