C++程序找到左右旋转相同的一个数字的最长子序列

在给定一个数字序列中，找到一个最长的子序列，该子序列在序列左旋转或右旋转后与原序列相同。

问题概述

在问题中，给定一个数字序列，我们需要找到一个子序列，该子序列在序列左旋转或右旋转后与原序列相同。例如，对于序列[1,2,3,4,5,6,7]，[3,4,5,6,7,1,2]就是一个符合要求的子序列。

问题的详细描述是，给定一个长度为n的数字序列a[1],a[2],…,a[n]，我们需要找到由原序列中的若干个元素组成的子序列，将该子序列左旋转或右旋转后，与原序列相同。

举一个例子，假设序列为1,2,3,4,5,6,7，其中左旋转后的序列为4,5,6,7,1,2,3。我们可以将原序列中的子序列2,3,4,5作为目标子序列，在旋转后，该子序列的位置变为4,5,6,7,1,2,3，与左旋转后的序列相同。

解决方案

暴力枚举法

对于任意给定的子序列，我们可以暴力枚举出所有旋转方式并比较与原序列是否相同。具体实现如下：

#include<bits/stdc++.h>
using namespace std;
int n,ans;
int a[100005],b[100005];
bool check(int x,int y)
{
    for(int i=1;i<=(y-x+1)/2;i++)
    {
        if(a[x+i-1]!=a[y-i+1]) return 0;
    }
    return 1;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=n;i++)
    {
        for(int j=i;j<=n;j++)
        {
            if(check(i,j))
            {
                for(int k=1;k<=n;k++) b[k]=a[k];
                reverse(b+i,b+j+1);
                bool ok=1;
                for(int k=1;k<=n;k++)
                {
                    if(a[k]!=b[k])
                    {
                        ok=0;
                        break;
                    }
                }
                if(ok) ans=max(ans,j-i+1);
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

说明：上述代码中，check函数用来判断给定的子序列是否符合要求，具体实现中，我们通过判断该子序列是否是左旋转或右旋转后的原序列的一部分来确认。接下来，我们枚举所有的子序列，并在确认符合要求的子序列后将其全部旋转，最后再与原序列进行比较。

时间复杂度：O(n^3)

哈希法

在哈希法中，我们需要用到一个函数，它可以将给定的数字序列转化为一个哈希值。这里我们使用Rabin-Karp算法来实现该函数。下面是详细实现，具体实现中，我们将哈希函数的计算结果存储在一个pair类型的数组中，检测子序列是否旋转后与原序列相同时，只需要比较两侧的哈希值即可。

#include<bits/stdc++.h>
#define p 10007
#define mod 99999997
using namespace std;
int n,ans,len;
int a[100005],b[100005];
pair<long long,long long> f[100005],g[100005],sum[100005],um[100005];
int check(int x,int y)
{
    if(x>y) return 0;
    int t=sum[y].second-sum[x-1].second*f[n-x+1].first;
    if(sum[n].second-sum[y].second==sum[y].first*(sum[n].first-sum[x-1].first)%mod)
    {
        return 1;
    }
    else if(um[x-1].second-um[n-y].second==um[n-y].first*(um[x-1].first-um[n-y+1].first)%mod)
    {
        return -1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++) 
    {
        cin>>a[i];
        a[n+i]=a[i];
    }
    for(int i=1;i<=n*2;i++)
    {
        f[i].first=(f[i-1].first*p+a[i])%mod;
        g[n*2-i+1].first=(g[n*2-i+2].first*p+a[n*2-i+1])%mod;
    }
    for(int i=1;i<=n*2;i++)
    {
        f[i].second=(f[i-1].second+p*f[i-1].first)%mod;
        g[n*2-i+1].second=(g[n*2-i+2].second+p*g[n*2-i+2].first)%mod;
    }
    for(int i=1;i<=n*2;i++)
    {
        sum[i].first=(sum[i-1].first+f[i].first)%mod;
        sum[i].second=(sum[i-1].second+f[i].second)%mod;
        um[i].first=(um[i-1].first+g[i].first)%mod;
        um[i].second=(um[i-1].second+g[i].second)%mod;
    }
    for(int i=1;i<=n/2;i++)
    {
        int l=i,r=n-i+1;
        while(r-l>=3)
        {
            int mid=(l+r)>>1;
            if(check(mid-i+1,2*n-r+mid))
            {
                l=mid;
            }
            else
            {
                r=mid;
            }
        }
        for(int j=r;j>=l;j--)
        {
            if(check(j-i+1,2*n-r+j))
            {
                ans=max(ans,j-i+1);
                break;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}

说明：上述的哈希法中，我们使用了Rabin-Karp算法，该算法可以将序列转化为一个哈希值。具体实现中，我们对原序列进行复制，并将复制后的序列与原序列合并在一起。然后，我们使用哈希函数将转化后的序列哈希化，并对哈希值进行预处理，确认哈希值的正确性，并使用查找查询确定子序列在旋转后是否与原序列相同。

时间复杂度：O(n(logn)^2)