Chrysanthemum's Blog

首先[tex]\sqrt n[/tex]枚举答案长度，在n枚举起点。接下来就是验证是否可行了。一开始想了一个错误的贪心，还自以为能A。。。

其实我们可以用区间DP来判断。

首先我们定义一下完美匹配。区间[i,j]是完美匹配当且仅当在用最优的方法删去一些模式串后，剩余的是模式串的前缀。显然如果区间长度是模式串的长度倍数又是完美匹配，那就符合条件。

完美匹配可以这样转移，将[i,j]分为[i,k],[k+1,j]只要两段都是完美匹配且至少有一段的长度是区间长度的倍数，这是一种转移。

还有一种转移是，[i,j-1]是完美匹配，且j处的字符为[i,j-1]的前缀的下一位，也就是模式串的第(（j-i)%len+1)位，len是模式串的长度。

这样转移是l/len的复杂度的，加点乱七八糟的优化就能过了。

代码：

#include<set>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int T,l,ans;
int f[210][210];
set<string> st;
char s[510],str[510];
int compare(int x,int len)
{
    for (int i=0;i<len;i++)
        if (s[i+x]>str[i]) return 1;else
        if (s[i+x]<str[i]) return -1;
    return 0;
}
void judge(int len)
{
    if (len>ans) return;
    for (int L=0;L<l;L++)
    if (L+len-1==l) break;else
    if (s[L]==s[0]&&s[L+len-1]==s[l-1])
    {
        string s1;
        s1.clear();
        for (int i=0;i<len;i++)
            s1+=s[L+i];
        if (st.count(s1)) continue;
        st.insert(s1);
        memset(f,0,sizeof(f));
        for (int i=0;i<l;i++) if (s[i]==s[L]) f[i][i]=1;
        for (int p=2;p<=l;p++)
            for (int i=0;i<l-p+1;i++)
            {
                int j=i+p-1;
                f[i][j]|=f[i][j-1]&(s[L+(p-1)%len]==s[j]);
                if (f[i][j]) continue;
                for (int k=1;k<=p/len;k++)
                {
                    f[i][j]|=f[i][i+k*len-1]&f[i+k*len][j];
                    f[i][j]|=f[j-k*len+1][j]&f[i][j-k*len];
                    if (f[i][j]) break;
                }
            }
        if (f[0][l-1])
        {
            if ((len<ans)||(len==ans&&(compare(L,len)<0)))
            {
                ans=len;
                for (int i=0;i<len;i++)
                    str[i]=s[L+i];
            }
        }
    }
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%s",s);
        l=strlen(s);
        ans=l+1;
        st.clear();
        for (int i=1;i*i<=l;i++)
        if (l%i==0)
        {
            judge(i);
            if (i*i!=l) judge(l/i);
        }
        for (int i=0;i<ans;i++)
            printf("%c",str[i]);
        printf("\n");
    }
}