Meepo的博客

题目大意

找到一个字符串中所有前半等于后半的字符串，如abab，按长度从短到长删除其左半部分，如果长度相等，则先删最左边的。
输出删除后剩余的字符串。

输入文件第一行包含整数 n，表示字符串的长度。 下面一行包含 n 个由空格隔开的在 0 到 10^9 范围内的数字，数字表示字符串中的字符。 数据保证每个字符在字符串中最多出现 10 次。

1<=n<=100000

显然我需要先找到所有符合条件的字符串，然后删除。
怎么判断一个字符串是否合法？
当然是哈希啦。
然后每个字符出现次数不超过10，我可以存下来，然后直接找。
找到每个合法字符的复杂度大概是O(n)的。

然后排个序，按顺序模拟就行了。
为什么我当时忘了每个字符出现次数不超过10的限制，给O(n^2)判了。

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <iostream>

using namespace std;
typedef unsigned long long ull;
const int N=100005;
const int bas=107;
const int INF=1e9+7;

int k;
ull hs[N],base[N];
int s[N],ss[N],s1[N];int tot;
int n;
int ans[N],res;
int st[N][15];
inline void dis()
{
    sort(ss+1,ss+1+n);
    for(int i=1;i<=n;++i) if(i==1||ss[i]!=ss[i-1]) s1[++tot]=ss[i];
}
inline int f(int x){return lower_bound(s1+1,s1+1+tot,x)-s1;}
struct data
{
    int l,r,len;
    friend bool operator <(data x,data y)
    {
        if(x.len==y.len) return x.l<y.l;
        return x.len<y.len;
    }
}a[N];int cnt;
int main()
{
    base[0]=1;
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&s[i]),ss[i]=s[i];
    dis(); 
    for(int i=1;i<=n;++i)
    {
        int val=f(s[i]);
        st[val][0]++;st[val][st[val][0]]=i;
    }
    for(int i=1;i<=n;++i) base[i]=base[i-1]*bas;
    for(int i=1;i<=n;++i) hs[i]=hs[i-1]*bas+s[i];

    for(int i=1;i<=n;++i)
    {
        int val=f(s[i]);
        for(int j=1;j<=st[val][0];++j)
        {
            int nxt=st[val][j];if(nxt<=i) continue;
            int len=nxt-i-1;
            ull x=hs[i+len]-hs[i-1]*base[len+1];
            ull y=hs[nxt+len]-hs[nxt-1]*base[len+1];
            if(x==y)
            {
                a[++cnt].l=i;a[cnt].r=nxt;a[cnt].len=nxt+len-i+1;
                break;
            }
        }
    }
    sort(a+1,a+1+cnt);
    int pos=0;
    for(int i=1;i<=cnt;++i)
    {
        int l=a[i].l;
        if(l<pos) continue;
        pos=a[i].r;
    }
    printf("%d\n",n-pos+1);
    for(int i=pos;i<=n;++i) printf("%d ",s[i]);
}