[Zero]

Hi,

I need help! I'm trying to implement a glob pattern generator, that would take a list of strings as input, and that would output the longest glob pattern that matches those strings.

Code: text

input:
    so I have a car
    so I have a bicycle
    so you have a car

output:
    so * have a *

Is there such a tool already somewhere?

[infurl]

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem

Here's a detailed description of the algorithm that you need to use. It contains lots of pseudocode which you should be able to convert into the language that you are using. I searched for ready-made libraries too but didn't find any. Try searching directly on github, you might have better luck than I did.

[infurl]

http://www.rosettacode.org/wiki/Longest_common_substring

I just thought of looking on rosettacode.org and sure enough, they have the algorithm implemented there, in just about every language you could think of no less. Good luck!

[Zero]

Thanks, I already know the LCS algo, but it's not what I want to achieve. I actually used it as part of my glob generator and successfully got globs from 2 strings, but not from N strings... yet!

Thank you!

[infurl]

https://en.wikipedia.org/wiki/Longest_common_subsequence_problem#Complexity

For the general case of an arbitrary number of input sequences, the problem is NP-hard.[1] When the number of sequences is constant, the problem is solvable in polynomial time by dynamic programming.

Oh dear, it does like a tricky one doesn't it.

[ivan.moony]

I'm not completely sure, but shouldn't it work like this: let's say we have to compare strings A, B, C, and D. First we compare A and B, then A and C, then A and D. Along the comparing, we accumulate differences into an array.

[Zero]

Oh dear, it does like a tricky one doesn't it.

NP-hard? ouch... I need NP-tough help 

I'm not completely sure, but shouldn't it work like this: let's say we have to compare strings A, B, C, and D. First we compare A and B, then A and C, then A and D. Along the comparing, we accumulate differences into an array.

Yes, or even cross-comparing them all, but it doesn't yield an obvious answer yet.

[Zero]

Code: javascript

function lcs(S, T) {
    
	var D = [];
	var LCS_len = 0;
	var LCS = [];

	for (var i = 0; i < S.length; i++) {
		D[i] = [];
		for (var j = 0; j < T.length; j++) {
			if (S[i] == T[j]) {
				if (i == 0 || j == 0) {
					D[i][j] = 1;
				} else {
					D[i][j] = D[i-1][j-1] + 1;
				}

				if (D[i][j] > LCS_len) {
					LCS_len = D[i][j];
					LCS = [S.substring(i-LCS_len+1, i+1)];
				} else if (D[i][j] == LCS_len) {
					LCS.push(S.substring(i-LCS_len+1, i+1));
				}
			} else {
				D[i][j] = 0;
			}
		}
	}
	return LCS[0];
}



function multiLcs(strings) {
    
    let candidate = strings[0];
    
    for (let str1 of strings)
        for (let str2 of strings) {
            let subs = lcs(str1, str2);
            if (!subs) return '';
            if (subs.length < candidate.length)
                candidate = subs;
        }
    return candidate;
}



function recurGenGlob(strings) {

    let center = multiLcs(strings);
    
    if (center.length == '') return '';
    
    let pre = strings.map(str => str.slice(0, str.indexOf(center)));
    let post = strings.map(str => str.slice(str.indexOf(center) + center.length));
    
    center = recurGenGlob(pre) + '*' + center + '*' + recurGenGlob(post);
    
    return center;
}



function genGlob(strings) {
    
    let center = recurGenGlob(strings.map(s => '  '+s+'  '));
    let result = '';
    let star = false;
    for (let i = 0; i < center.length; i++) {
        if (center[i] != '*' || star)
            result += center[i];
        star = center[i] == '*';
    }
    return result.trim();
}

[ivan.moony]

Does that work?

[Zero]

I don't know. It does spit something out, but I believe it's not optimal.

Edit: I mean, I believe the returned value of genGlob() is not always the longest possible pattern. It needs testing. But since it's Js, you can directly copy-paste it in your browser's console ang give it a shot: at least for the example I gave in the original post, it works (better than me, since I forgot the common 'c' in 'car' and 'bicycle', my own hand-made output was wrong). The trim() trick is a bit hacky though.

[Zero]

doesn't work with

Code

    "and so I have a car",
    "so I have a bicycle",
    "so you have a car",

[Zero]

Here is the new corrected genGlob().

Code: javascript

genGlob = (strings) => {
    
    let center = recurGenGlob(strings);

    while (center.indexOf('**') > -1)
        center = center.replace(/\*\*/g, '*');

    let startStar = false,
        endStar = false,
        startLetter = strings[0][0],
        endLetter = strings[0][strings[0].length-1];
        
    for (let s of strings) {
        if (s[0] != startLetter) startStar = true;
        if (s[s.length-1] != endLetter) endStar = true;
    }
    
    if (!startStar) center = center.slice(1);
    if (!endStar) center = center.slice(0, -1);

    if (center.length == 0) center = '*';

    return center;
}

[8pla.net]

I may I know how. Are you OK with PHP?

[Zero]

I believe my JS is correct, but yes I'm OK with PHP.

[frankinstien]

This will work with any N number of words and sentences:

Code

using System;
using System.Collections.Generic;
using System.Linq;
					
public class Program
{
	public static void Main()
	{
		List<string> alreadyCounted = new List<string>();
			var counts = new Dictionary<string, int>();
			string[] sets = new string[] { "so I have a car, but this car is used", "so I have a bicycle", "so you have a car" };
			foreach (String aSet in sets)
			{
				var sentenceSplit = aSet.Split(new char[] { ' ', ',' });
				alreadyCounted.Clear();
				foreach (String aWord in sentenceSplit)
				{
					var trimmed = aWord.Trim();
					if (counts.ContainsKey(trimmed) && !alreadyCounted.Contains(trimmed))
						counts[trimmed] = counts[trimmed] + 1;
					else if(!alreadyCounted.Contains(trimmed))
						counts.Add(trimmed, 1);
					alreadyCounted.Add(trimmed);
				}				
			}

			var results = counts.Where(x => x.Value == sets.Length);
			if (results != null)
			{
				foreach (KeyValuePair<string, int> entry in results)
					Console.WriteLine(entry.Key);
			}
	}
}

Try it on Fiddle: https://dotnetfiddle.net/

Its a small mod to get it to work with a file where you just load the file into the string array.