algorithm - 在集合中寻找模式

Question

我可以使用什么算法来确定一组字符串中的常见字符？

为了简化示例，我只关心连续 2 个以上的字符以及它是否出现在 2 个或更多示例中。例如:

1. 0000abcde0000
2. 0000abcd00000
3. 000abc0000000
4. 00abc000de000

我想知道:

00被用于1,2,3,4
1,2,3,4中使用了000
1,2,3中使用了0000
00000 用于 2,3
ab被用在1,2,3,4
abc被用在1,2,3,4
1,2中使用了abcd
bc被用在1,2,3,4
1,2中使用了bcd
cd被用在1,2
de 用于 1,4

Answer 1

我假设这不是家庭作业。 (如果是，那你就是你自己再抄袭了!;-)

下面是一个快速而简单的解决方案。时间复杂度为 O(m**2 * n) 其中 m 是平均字符串长度，n 是数组的大小字符串。

Occurrence 的实例保留包含给定字符串的索引集。 commonOccurrences 例程扫描字符串数组，为每个非空字符串调用 captureOccurrences。 captureOccurrences 例程将当前索引放入 Occurrence 中，用于给定字符串的每个可能子字符串。最后，commonOccurrences 通过仅选择那些至少有两个索引的 Occurrences 形成结果集。

请注意，您的示例数据具有比您在问题中确定的更多的常见子字符串。例如，"00ab" 出现在每个输入字符串中。根据内容(例如所有数字、所有字母等)选择有趣字符串的附加过滤器——正如他们所说——留给读者作为练习。 ;-)

快速而肮脏的 JAVA 源代码:

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);
        }
    }

}

示例输出:(请注意，实际上每行只有一次出现；我似乎无法阻止 blockquote 标记合并行)

"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 "00a": 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
"0a": 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 "bc": 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 "cd": 0,1
"de": 0,3 "de0": 0,3 "de00": 0,3
"e0": 0,3 "e00": 0,3