c# - 是否有一种算法(名称、实现)给出两个相同排序/内容但不同起始项的列表来测试是否相等？

Question

肯定有一些东西在那里，但谷歌搜索并没有给我我正在寻找的东西。可能是因为我不知道要查找的算法的名称？

基本上，我有两个内容和大小相同的列表。

List1: {10, 30, 2, 4, 4}
List2: {4, 4, 10, 30, 2}

请注意，两个列表的顺序相同。即:List2可以看做是从List1的上一个位置到最后一个位置开始，从List1的开头继续迭代，直到回到起始位置。

List1: {10, 30, 2, 4, 4} 10, 30, 2
                   |  |  |   |   |
List2:            {4, 4, 10, 30, 2}

然后这两个列表被认为是等价的。

以下两个列表不是:

List1: {10, 30, 2, 4, 3} 10, 30, 2
                   |  |  X   X   |
List2:            {4, 4, 30, 10, 2}

更新

我现在正在做的是将 List1 连接到自身并在其中搜索 List2。

我觉得这是低效的。

假设我想对每个列表进行一次迭代？

更新

好的，最后我使用了描述于以下位置的算法:Check if a string is rotation of another WITHOUT concatenating并使其适应我的数据类型。

Answer 1

在 List1+List1 中搜索 List2。您可以使用 KMP在线性时间内做到这一点。

更新:优化代码，在最好的情况下至少与其他解决方案一样快，在最坏的情况下速度惊人地快

一些代码。该代码使用 KMP 的修改版本，它接收 List1，但实际上认为它已经加倍(为了性能)。

using System;
using System.Collections.Generic;
using System.Linq;

namespace Test
{
    public class CyclicKMP<T> {
        private readonly IList<T> P;
        private readonly int[] F;
        private readonly EqualityComparer<T> comparer;

        public CyclicKMP(IList<T> P) {
            this.comparer = EqualityComparer<T>.Default;
            this.P = P;
            this.F = new int[P.Count+1];

            F[0] = 0;  F[1] = 0;  
            int i = 1, j = 0;
            while(i<P.Count) {
                if (comparer.Equals(P[i], P[j]))
                    F[++i] = ++j;
                else if (j == 0)
                    F[++i] = 0;
                else
                    j = F[j];
            }
        }

        public int FindAt(IList<T> T, int start=0) {
            int i = start, j = 0;
            int n = T.Count, m = P.Count;

            while(i-j <= 2*n-m) {
                while(j < m) {
                    if (comparer.Equals(P[j], T[i%n])) {
                        i++; j++;
                    } else break;
                }
                if (j == m) return i-m;
                else if (j == 0) i++;
                j = F[j];
            }
            return -1;
        }
    }

    class MainClass
    {
        public static bool Check<T>(IList<T> list1, IList<T> list2) {
            if (list1.Count != list2.Count)
                return false;
            return new CyclicKMP<T> (list2).FindAt (list1) != -1;
        }

        public static void Main (string[] args)
        {
            Console.WriteLine (Check(new[]{10, 30, 2, 4, 4}, new[]{4, 4, 10, 30, 2}));
            Console.WriteLine (Check(new[]{10, 30, 2, 4, 3}, new[]{4, 4, 10, 30, 2}));
        }
    }
}