Find occurrence count of longest common prefix/suffix in list of Strings?-CodePudding

The

The two first lines will constitute a cluster formed from a linked list (the head part) and a tree (the tail part). The second cluster will be represented by a linked list (i.e. consists from the head part only), its vertices aren't connected with vertices formed from other strings.

For this task, we are interested in the parts of the graph where vertexes overlap. Each string at the beginning and at the end of each line that a common with other string will be represented by a single vertex (node). In order to maintain the number of strings that are mapped to a particular vertex, each vertex should maintain a variable (int groupCount in the code below), which is assigned with a default value of 1 when a vertex is being created and incremented each time a new string get mapped to this vertex.

Each vertex contains a map that holds references to its neighbuors. When a new neighbuor-vertex is being added, either new Vertex in being created based on the given string or the count of an existing vertex gets incremented.

In order to conform to this task, the graph should maintain references to all head-vertexes and tail-vertexes. For simplicity, instead of maintaining two groups of references to adjacent nodes, and two separate count variables (because suffix-count and prefix-count will differ) in each vertex, in this solution graph is actually comprised of two graph (suffix-graph and prefix-graph).

The following implementation consists of two classes that are narrow-focused and self-contained. The MultiGraph class acts exclusively as data structure, maintaining two graphs. The pluming code, like splitting the lines of strings, is extracted into a separate class GraphManager.

Graph

public class MultiGraph { private final Map<String, Vertex> heads = new HashMap<>(); private final Map<String, Vertex> tails = new HashMap<>(); public void addCluster(Deque<String> names) { addCluster(heads, names.iterator()); addCluster(tails, names.descendingIterator()); } private void addCluster(Map<String, Vertex> clusters, Iterator<String> names) { String rootName = names.next(); if (clusters.containsKey(rootName)) { clusters.get(rootName).incrementGroupCount(); } else { clusters.put(rootName, new Vertex(rootName)); } Vertex current = clusters.get(rootName); while (names.hasNext()) { current = current.addNext(names.next()); } } public Map<String, Integer> generatePrefixMap(String delimiter) { Map<String, Integer> countByPrefix = new HashMap<>(); for (Vertex next: heads.values()) { if (next.getGroupCount() == 1) { continue; } performDFS(heads, countByPrefix, delimiter, next); } return countByPrefix; } public Map<String, Integer> generateSuffixMap(String delimiter) { Map<String, Integer> countBySuffix = new HashMap<>(); for (Vertex next: tails.values()) { if (next.getGroupCount() == 1) { continue; } performDFS(tails, countBySuffix, delimiter, next); } return countBySuffix; } // implementation of the Depth First Search algorithm public void performDFS(Map<String, Vertex> clusters, Map<String, Integer> countByPrefix, String delimiter, Vertex next) { StringBuilder prefix = null; Vertex current = next; int count = next.getGroupCount(); Deque<Vertex> stack = new ArrayDeque<>(); Map<Vertex, StringBuilder> prefixByVert = new HashMap<>(); stack.push(next); prefixByVert.put(current, new StringBuilder(current.getName())); while (!stack.isEmpty()) { current = stack.pop(); if (current.getGroupCount() < count) { if (current.getGroupCount() == 1) { current = stack.pop(); } countByPrefix.put(prefix.toString(), count); // saving the result count = current.getGroupCount(); } prefix = prefixByVert.get(current); for (Vertex neighbour: current.getNextVertByVal().values()) { if (next.getGroupCount() == 1) { continue; } stack.push(neighbour); prefixByVert.put(neighbour, new StringBuilder(prefix) .append(delimiter) .append(neighbour.getName())); } } if (prefix != null && count > 1) { countByPrefix.putIfAbsent(prefix.toString(), count); } } private static class Vertex { private final String name; private int groupCount = 1; private final Map<String, Vertex> nextVertByVal = new HashMap<>(); public Vertex(String name) { this.name = name; } public Vertex addNext(String value) { if (nextVertByVal.containsKey(value)) { nextVertByVal.get(value).incrementGroupCount(); } else { nextVertByVal.put(value, new Vertex(value)); } return nextVertByVal.get(value); } public void incrementGroupCount() { this.groupCount ; } public String getName() { return name; } public int getGroupCount() { return groupCount; } public Map<String, Vertex> getNextVertByVal() { return nextVertByVal; } } }

GraphManager

public class GraphManager { private MultiGraph graph = new MultiGraph(); private String delimiter; private GraphManager(String delimiter) { this.delimiter = delimiter; } public static GraphManager getInstance(Iterable<String> lines, String delimiter) { GraphManager gm = new GraphManager(delimiter); gm.init(lines); return gm; } private void init(Iterable<String> lines) { for (String line: lines) { Deque<String> names = new ArrayDeque<>(); for (String name: line.split(delimiter)) { if (!name.isEmpty()) { names.add(name); } } addCluster(names); } } private void addCluster(Deque<String> names) { graph.addCluster(names); } public Map<String, Integer> getPrefixMap() { return graph.generatePrefixMap(delimiter); } public Map<String, Integer> getSuffixMap() { return graph.generateSuffixMap(delimiter); } }

main()

public static void main(String[] args) { List<String> lines = List.of( "Mary had a little lamb named Willy", "Mary had a little ham", "Old McDonald had a farm named Willy", "Willy had a little dog named ham", "( abc )", "( xyz )", "Visit Target Store", "Visit Walmart Store"); GraphManager gm = GraphManager.getInstance(lines, " "); System.out.println("Prefixes:"); gm.getPrefixMap().entrySet().stream() .sorted(Map.Entry.<String, Integer>comparingByValue().reversed()) .forEach(entry -> System.out.println(entry.getValue() " " entry.getKey())); System.out.println("\nSuffixes:"); gm.getSuffixMap().entrySet().stream() .sorted(Map.Entry.<String, Integer>comparingByValue().reversed()) .forEach(entry -> System.out.println(entry.getValue() " " entry.getKey())); }

Output

Prefixes: 2 Mary had a little 2 Visit 2 ( Suffixes: 2 ham 2 ) 2 Store 2 Willy named