# Clustering strings inside strings?

I am not sure whether I formulated the question correctly. Basically, what I want to do is:

Let's suppose I have a list of 1000 strings which look like this:

cvzxcvzxstringcvzcxvz

otortorotrstringgrptprt

vmvmvmeopstring2vmrprp

vccermpqpstring2rowerm

proorororstring3potrprt

mprto2435string3famerpaer

etc.

I'd like to extract these reoccuring strings that occur on the list. What solution should I use? Does anyone know about algorithm that could do this?

• How do you decide that "string", "string2" and "string3" are similar, but "string", "xstring" and "stringg", for example, are not? Commented Oct 23, 2014 at 19:12
• As I understood it, string, string2 and string3 are placeholders; they are not necessarily similar.
– Emre
Commented Oct 23, 2014 at 20:05
• By string similar I mean they are exactly the same, char by char. Additionally, there might be multiple pairs of exact substrings between the two strings. Commented Oct 24, 2014 at 5:58
• No, the question is if there is another string that has "stringg" then if and how is it different from string2 or string3? The question is about defining EXACTLY what you want to do. Like is there a minimum length of strings you're looking to cluster? Is there a maximum length? Commented Oct 27, 2014 at 15:23
• I've implemented longest common substring algorithm. It solved my problem but it's expensive computationally. Commented Oct 28, 2014 at 8:28