Topic link: poj1743

The main idea of the title;

Give you a sequence of numbers with length n. Ask you to find the longest length of the sequence that meets the following requirements:

The length of two sequences is greater than or equal to 5

There are two non-overlapping sequences in the original sequence.

These two sequences are of the same length and the second sequence can be obtained by adding a constant to all the numbers of the first sequence.

This topic can be seen in Luo Suiqian's Suffix Array: A Powerful Tool for String Processing. Click Open Link

First of all, we need a non-overlapping sequence of at least 5 in length. In fact, the similarity between the two sequences is equal to the increase of the adjacent elements in their two sequences. So we can get a new array of length n-1 by subtracting the last number of primitive arrays of length n from the previous one.

Then, in this new array, we just need to find the longest continuous string that does not overlap twice.

The above problem can be solved by using suffix arrays. We turn the above problem into a decision question: Is there a non-overlapping subsequence of length k?

Firstly, we find the sa and height of the new array, and then divide the suffixes sorted by n (the new array n-1, but need to add the tail 0 to become n) into several groups, preserving the heights >= K in each group. If there are repetitive non-overlapping subsequences of k, then it must be two prefixes of the same suffixes. If there is a difference between the maximum value of sa and the minimum value of sa > k in a group, then there exists a suffix > K. Such a sequence, otherwise K would not be appropriate.

Next, there is a point to be noted: the subject data is not strong, and many of the codes on the Internet are incorrect.

• First, the problem is transformed into the problem of repeated substrings: each bit of the original string is subtracted from the previous one. If two substrings of length n are the same, then they are similar to the substrings of length n+1 of the original string.
• So the next requirement is that the new string should not "overlap" the longest repetitive substring - the problem is here, which requires not only that the two substrings should not overlap, but also that the two substrings should be separated at least one location, because if the two substrings are close together, it reflects that the two substrings of the original string are overlapping at the beginning and the end.

For example, data: 9 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

At least one location apart from the original if (mx-mm >= k) is changed to if (mx-mm > k).

 

Finally, a general description of the solution of the non-overlapping longest repeated substring is given.

• O(logn) Dichotomous Enumeration Substring Length to Judge the Validity of Solution
• O(n) Judging whether the length is valid: divide the LCP greater than or equal to the length of each other into groups, which can be done by sweeping the height once, because the suffixes are orderly and the LCP between adjacent suffixes must be great; Next, find the maximum and minimum suffixes sa value in each group, if the difference is greater than (equal to) k, it will be valid, because the suffixes with small subscripts go down the LCP to K. Step will not cover the suffix of the big subscript.

Next, a sample is provided to test.

11
1 2 3 4 5 6 7 8 9 10 11

The correct answer is 5. Some codes on the Internet answer 6, even can ac

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=20000+100;
const int maxm=20000+100;
struct SuffixArray
{
    int s[maxn];
    int sa[maxn],rank[maxn],height[maxn];
    int t1[maxn],t2[maxn],c[maxm],n;
    void build_sa(int m)
    {
        int i,*x=t1,*y=t2;
        for(i=0;i<m;i++) c[i]=0;
        for(i=0;i<n;i++) c[x[i]=s[i]]++;
        for(i=1;i<m;i++) c[i]+=c[i-1];
        for(i=n-1;i>=0;i--) sa[--c[x[i]]]=i;
        for(int k=1;k<=n;k<<=1)
        {
            int p=0;
            for(i=n-k;i<n;i++) y[p++]=i;
            for(i=0;i<n;i++)if(sa[i]>=k) y[p++]=sa[i]-k;
            for(i=0;i<m;i++) c[i]=0;
            for(i=0;i<n;i++) c[x[y[i]]]++;
            for(i=1;i<m;i++) c[i]+=c[i-1];
            for(i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i];
            swap(x,y);
            p=1;
            x[sa[0]]=0;
            for(i=1;i<n;i++)
                x[sa[i]]= y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]? p-1:p++;
            if(p>=n) break;
            m=p;
        }
    }
    void build_height()
    {
        int i,j,k=0;
        for(i=0;i<n;i++) rank[sa[i]]=i;
        for(i=0;i<n;i++)
        {
            if(k)k--;
            j=sa[rank[i]-1];
            while(s[i+k]==s[j+k]) k++;
            height[rank[i]]=k;
        }
    }
    bool check(int k)//String with long l appearing more than k times
    {
        int maxe,mine;
        maxe=mine=sa[1];
        for(int i=2;i<n;i++)
        {
            if(height[i]<k)
                maxe=mine=sa[i];
            else
            {
                maxe=max(maxe,sa[i]);
                mine=min(mine,sa[i]);
                if(maxe-mine>k) return true;
                //At least one empty in the middle prevents two sequences from joining at the beginning and the end
            }
        }
        return false;
    }
}sa;

int main()
{
    int n;
    int m,k;
    while(scanf("%d",&n)==1&&n)
    {
    	scanf("%d",&m);
        for(int i=0;i<n-1;i++)
        {
            scanf("%d",&k);
            sa.s[i]=k-m+100;
            m=k;
        }
        if(n<10)
		{
			printf("0\n");
			continue;
		}
        sa.s[n-1]=0;
        sa.n=n+1;
        sa.build_sa(200);
        sa.build_height();
        if(!sa.check(4))
		{
			printf("0\n");
			continue;
		}
        int min=1,max=sa.n/2;
        int ans;
        while(min<=max)
        {
            int mid=(max+min)>>1;
            if(sa.check(mid))
			{
				ans=mid;
				min = mid+1;
			}
            else max=mid-1;
        }
        printf("%d\n",ans+1);
    }
    return 0;
}