题目描述

Description

有三个好朋友喜欢在一起玩游戏,A君写下一个字符串S,B君将其复制一遍得到T,C君在T的任意位置(包括首尾)插入一个字符得到U.现在你得到了U,请你找出S.

Input

第一行一个数N,表示U的长度.
第二行一个字符串U,保证U由大写字母组成

Output

输出一行,若S不存在,输出"NOT POSSIBLE".若S不唯一,输出"NOT UNIQUE".否则输出S.

Sample Input1:

7
ABXCABC

Sample Input2:

6
ABCDEF

Sample Input3:

9
ABABABABA

Sample Output1:

ABC

Sample Output2:

NOT POSSIBLE

Sample Output3:

NOT UNIQUE

HINT

对于100%的数据 2<=N<=2000001

题目分析

首先S串如果存在，一定是U串（长度姑且设为2n+1，偶数则直接impossible）的[1,n]或者[n+2,2n+1]。。
然后我们可以暴力匹配，允许一次失配（就是第一次失配就跳过接着匹配。）
然后如果匹配完全串了，就是一种可行S串。
然后如果正着反着都成功了，可能U串是 S+一个字符+S。需要特判。

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,flag1,flag2;
char s[3001000];
int check1()
{
    int nmp=1,tmp=n/2+1,now=-1,i;
    for(i=tmp;i<=n;i++)
    {
        if(s[i]!=s[nmp])
        {
            if(now!=-1) return -1;
            else if(now==-1) now=i;
        }
        else nmp++;
        if(nmp>n/2) break;
    }
    if(nmp>n/2&&now==-1) now=n;
    return now;
}
int check2()
{   
    int nmp=n-n/2+1,tmp=1,now=-1,i;
    for(i=tmp;i<=n/2+1;i++)
    {
        if(s[i]!=s[nmp])
        {
            if(now!=-1) return -1;
            else if(now==-1) now=i;
        }
        else nmp++;
        if(nmp>n) break;
    }
    if(nmp>n&&now==-1) now=n/2+1;
    return now;
}
int main()
{
    scanf("%d",&n);
    scanf("%s",s+1);
    if(n%2==0)
    {
        printf("NOT POSSIBLE");
        return 0;
    }
    flag1=check1(),flag2=check2();
    if(flag1!=-1&&flag2!=-1)
    {
        int i;
        for(i=1;i<=n/2&&s[i]==s[i+n/2+1];i++);
        if(i<=n/2)puts("NOT UNIQUE");
        else for(i=1;i<=n/2;i++)printf("%c",s[i]);
    }
    else if(flag1==-1&&flag2==-1) printf("NOT POSSIBLE");
    else
    {
        if(flag1!=-1)
            for(int i=1;i<=n/2;i++) printf("%c",s[i]);
        else
            for(int i=n-n/2+1;i<=n;i++) printf("%c",s[i]);
    }
    return 0;
}