java - 搜索最长的重复字节序列

Question

使用字节我需要找到最长的重复序列。最长重复序列为23

2356238888

因为它从序列 8 开始在字节列表中按顺序出现两次。我决定沿着这条路行动。

1. 取出第一个数字并检查它是否在
   中的其他位置如果没有则列出，然后取下一个数字

2356238888

之后，我检查站立的数字是否与第一个是重合的，如果是，我把它们放在一个列表中，然后我继续检查(例如，如果两个 23 个数字重合)，如果我不重合然后我再取一个号码。

2356238888

我的方法

List<Byte> topList = new ArrayList<>(); // byte list
List<Byte> result = new ArrayList<>(); // result list
for (int i = 0; i < topList.size(); i += count) {
            count = 1;
            for (int j = i + 1; j < topList.size(); j += count) {
                if (topList.get(i).equals(topList.get(j))&& !result.contains(topList.get(j))) {
                    result.add(topList.get(i));
                    result.add(topList.get(j));
                    for (int k = j + 1; k < topList.size(); k++) {
                        if (topList.get(k).equals(topList.get(i + count)) ) {
                            result.add(topList.get(k));
                            System.out.println(result);
                            count++; // step to pass already checked numbers
                        }
                    }
                }
            }
        }

但是我的代码无法正常工作。

2238888

我得到了序列数据。告诉我如何改进它，你不能使用字符串

Answer 1

我没有看到任何O(n^2)解决方案的替代方案，其中，从输入中的每个位置开始，我们生成每个前向序列并检查我们是否已经看到它之前，保留时间最长。幸运的是，我们不需要考虑比当前最长序列短的序列，也不需要考虑比 n/2 更长的序列，其中 n 是大小输入的，因为这些不能重复。另外，我们不考虑破坏重复字符的序列，因为它们被视为不可分割的。

这是一个简单的实现，它使用Set来跟踪以前见过的序列。实际上，您希望使用更复杂的结构，更紧凑并利用元素中的模式，但这足以验证我们正在生成所需的输出。

static List<Byte> longestRepeatingSeq(List<Byte> in)
{
    int n = in.size();
    Set<List<Byte>> seen = new HashSet<>();
    List<Byte> max = Collections.<Byte> emptyList();
    for (int i=0; i<n; i++)
    {
        for (int j =i+max.size()+1; j<=n && j<=i +n/2; j++)
        {
            if (j == n || in.get(j) != in.get(j - 1))
            {
                List<Byte> sub = in.subList(i, j);
                if (seen.contains(sub))
                {
                    if (sub.size() > max.size())
                    {
                        max = sub;
                    }
                } 
                else
                {
                    seen.add(sub);
                }
            }
        }
    }
    return max;
}

测试:

public static void main(String[] args)
{
    String[] tests = 
        {
            "123123",
            "235623",
            "2356238888",
            "88388",
            "883883",
            "23235623238888",
        };

    for(String s : tests)
    {
        List<Byte> in = new ArrayList<>();
        for(String ns : s.split("")) in.add(Byte.parseByte(ns));
        System.out.println(s + " " + longestRepeatingSeq(in));
    }
}

输出:

123123 [1, 2, 3]
235623 [2, 3]
2356238888 [2, 3]
88388 [8, 8]
883883 [8, 8, 3]
23235623238888 [2, 3, 2, 3]