Я предполагаю, что это не домашняя работа. (Если это так, вы один из ваших собственных плагиата!; -)
Ниже приведено быстрое и грязное решение. Сложность по времени составляет O(m**2 * n), где m - средняя длина строки, а n - размер массива строк.
Экземпляр Occurrence содержит набор индексов, которые содержат данную строку. Подпрограмма commonOccurrences сканирует строковый массив, вызывая captureOccurrences для каждой ненулевой строки. Подпрограмма captureOccurrences помещает текущий индекс в Occurrence для каждой возможной подстроки строки, которая ему дана. Наконец, commonOccurrences формирует набор результатов, выбирая только те Occurrences, которые имеют как минимум два индекса.
Обратите внимание, что в данных вашего примера гораздо больше общих подстрок, чем вы указали в вопросе. Например, "00ab" встречается в каждой из входных строк. Дополнительный фильтр для выбора интересных строк на основе содержимого (например, все цифры, все буквы и т. Д.), Как говорится, оставлен в качестве упражнения для читателя. ; -)
ИСТОЧНИК БЫСТРОГО И Грязного Ява:
package com.stackoverflow.answers;
import java.util.Collections;
import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.TreeSet;
public class CommonSubstringFinder {
public static final int MINIMUM_SUBSTRING_LENGTH = 2;
public static class Occurrence implements Comparable<Occurrence> {
private final String value;
private final Set<Integer> indices;
public Occurrence(String value) {
this.value = value == null ? "" : value;
indices = new TreeSet<Integer>();
}
public String getValue() {
return value;
}
public Set<Integer> getIndices() {
return Collections.unmodifiableSet(indices);
}
public void occur(int index) {
indices.add(index);
}
public String toString() {
StringBuilder result = new StringBuilder();
result.append('"').append(value).append('"');
String separator = ": ";
for (Integer i : indices) {
result.append(separator).append(i);
separator = ",";
}
return result.toString();
}
public int compareTo(Occurrence that) {
return this.value.compareTo(that.value);
}
}
public static Set<Occurrence> commonOccurrences(String[] strings) {
Map<String,Occurrence> work = new HashMap<String,Occurrence>();
if (strings != null) {
int index = 0;
for (String string : strings) {
if (string != null) {
captureOccurrences(index, work, string);
}
++index;
}
}
Set<Occurrence> result = new TreeSet<Occurrence>();
for (Occurrence occurrence : work.values()) {
if (occurrence.indices.size() > 1) {
result.add(occurrence);
}
}
return result;
}
private static void captureOccurrences(int index, Map<String,Occurrence> work, String string) {
final int maxLength = string.length();
for (int i = 0; i < maxLength; ++i) {
for (int j = i + MINIMUM_SUBSTRING_LENGTH; j < maxLength; ++j) {
String partial = string.substring(i, j);
Occurrence current = work.get(partial);
if (current == null) {
current = new Occurrence(partial);
work.put(partial, current);
}
current.occur(index);
}
}
}
private static final String[] TEST_DATA = {
"0000abcde0000",
"0000abcd00000",
"000abc0000000",
"00abc000de000",
};
public static void main(String[] args) {
Set<Occurrence> found = commonOccurrences(TEST_DATA);
for (Occurrence occurrence : found) {
System.out.println(occurrence);
}
}
}
ОБРАЗЕЦ ВЫБОРА: (обратите внимание, что на строку в действительности приходился только один Вихрь; похоже, я не могу помешать разметке цитат из слияния строк)
"00": 0,1,2,3
«000»: 0,1,2,3
«0000»: 0,1,2
«0000a»: 0,1
«0000ab»: 0,1
«0000abc»: 0,1
«0000abcd»: 0,1
"000a": 0,1,2
«000ab»: 0,1,2
«000abc»: 0,1,2
"000abcd": 0,1
«00а»: 0,1,2,3
«00ab»: 0,1,2,3
«00abc»: 0,1,2,3
«00abc0»: 2,3
«00abc00»: 2,3
«00abc000»: 2,3
«00abcd»: 0,1
«0а»: 0,1,2,3
«0ab»: 0,1,2,3
«0abc»: 0,1,2,3
«0abc0»: 2,3
«0abc00»: 2,3
«0abc000»: 2,3
"0abcd": 0,1
"ab": 0,1,2,3
«abc»: 0,1,2,3
"abc0": 2,3
«abc00»: 2,3
«abc000»: 2,3
"abcd": 0,1
«до н.э.»: 0,1,2,3
"bc0": 2,3
"bc00": 2,3
"bc000": 2,3
"bcd": 0,1
"c0": 2,3
"c00": 2,3
"c000": 2,3
"кд": 0,1
"де": 0,3
"de0": 0,3
"de00": 0,3
"e0": 0,3
«е00»: 0,3