P3900 [湖南集训]图样图森破

链接

分析：

　　感觉像个暴力。

　　可以枚举回文串的回文中心，即枚举一个串，枚举一个串的位置作为回文中心，然后求出这个串内的回文串的长度。

　　此时如果回文串两端都没有到这个串的端点，那么以这个点作为回文中心的长度就直接算出来了。

　　如果回文串的长度刚好是这个串的长度，那么INF。

　　如果回文串一侧到了端点，那么枚举所有串，看看能否加到另一侧，来构成回文串。此过程记忆化搜索即可。

　　复杂度$O(nL \log nL)$

代码：

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

#include<cctype>

#include<set>

#include<queue>

#include<vector>

#include<map>

using namespace std;

typedef long long LL;

inline int read() {

    int x=,f=;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-;

    for(;isdigit(ch);ch=getchar())x=x*+ch-'';return x*f;

}

const int N = ;

int s[N], st[N], en[N], rnk[N], ht[N], sa[N], f[][N], Log[N], t1[N], t2[N], c[N], bel[N], dp[N][];

bool vis[N][];

char tmp[N];

int n, m;

void getsa() {

    int *x = t1, *y = t2, m = , i;

    for (i = ; i <= m; ++i) c[i] = ;

    for (i = ; i <= n; ++i) x[i] = s[i], c[x[i]] ++;

    for (i = ; i <= m; ++i) c[i] += c[i - ];

    for (i = n; i >= ; --i) sa[c[x[i]] --] = i;

    for (int k = ; k <= n; k <<= ) {

        int p = ;

        for (i = n - k + ; i <= n; ++i) y[++p] = i;

        for (i = ; i <= n; ++i) if (sa[i] > k) y[++p] = sa[i] - k;

        for (i = ; i <= m; ++i) c[i] = ;

        for (i = ; i <= n; ++i) c[x[y[i]]] ++;

        for (i = ; i <= m; ++i) c[i] += c[i - ];

        for (i = n; i >= ; --i) sa[c[x[y[i]]] --] = y[i];

        swap(x, y);

        p = ;

        x[sa[]] = ;

        for (i = ; i <= n; ++i)

            x[sa[i]] = (y[sa[i]] == y[sa[i - ]] && y[sa[i] + k] == y[sa[i - ] + k]) ? p -  : p ++;

        if (p > n) break;

        m = p;

    }

    for (int i = ; i <= n; ++i) rnk[sa[i]] = i;

    int k = ;

    ht[] = ;

    for (int i = ; i <= n; ++i) {

        if (rnk[i] == ) continue;

        if (k) k --;

        int j = sa[rnk[i] - ];

        while (i + k <= n && j + k <= n && s[i + k] == s[j + k]) k ++;

        ht[rnk[i]] = k;

    }

    Log[] = -;

    for (int i = ; i <= n; ++i) Log[i] = Log[i >> ] + ;

    for (int i = ; i <= n; ++i) f[][i] = ht[i];

    for (int j = ; j <= Log[n]; ++j)

        for (int i = ; i + ( << j) -  <= n; ++i)

            f[j][i] = min(f[j - ][i], f[j - ][i + ( << (j - ))]);

}

int query(int l,int r) {

    if (l == r) return 1e9;

    l = rnk[l], r = rnk[r];

    if (l > r) swap(l, r);

    l ++;

    int k = Log[r - l + ];

    return min(f[k][l], f[k][r - ( << k) + ]);

}

int getlcp(int x,int y) {

    return min(query(x, n - y + ), min(en[bel[x]] - x + , y - st[bel[y]] + ));

}

void End() {

    puts("Infinity"); exit();

}

int dfs(int x,int t) {

    if (vis[x][t]) End();

    if (dp[x][t]) return dp[x][t];

    vis[x][t] = ;

    if (!t) {

        for (int i = ; i <= m; ++i) {

            int k = getlcp(x, en[i]), l = en[i] - k + , r = x + k - ;

            if (r != en[bel[x]] && l != st[i]) dp[x][t] = max(dp[x][t], k * );

            else if (r == en[bel[x]] && l == st[i]) End();

            else if (r == en[bel[x]]) dp[x][t] = max(dp[x][t], k *  + dfs(l - , ));

            else dp[x][t] = max(dp[x][t], k *  + dfs(r + , ));

        }

    }

    else {

        for (int i = ; i <= m; ++i) {

            int k = getlcp(st[i], x), l = x - k + , r = st[i] + k - ;

            if (l != st[bel[x]] && r != en[i]) dp[x][t] = max(dp[x][t], k * );

            else if (l == st[bel[x]] && r == en[i]) End();

            else if (l == st[bel[x]]) dp[x][t] = max(dp[x][t], k *  + dfs(r + , ));

            else dp[x][t] = max(dp[x][t], k *  + dfs(l - , ));

        }

    }

    vis[x][t] = ;

    return dp[x][t];

}

int main() {

    m = read();

    for (int i = ; i <= m; ++i) {

        scanf("%s", tmp + );

        int len = strlen(tmp + );

        st[i] = n + ;

        for (int j = ; j <= len; ++j) s[++n] = tmp[j] - 'a' + , bel[n] = i;

        en[i] = n;

    }

    for (int i = ; i <= n; ++i) s[i + n] = s[n - i + ];

    n <<= ;

    getsa();

    int ans = ;

    for (int i = ; i <= m; ++i)

        ans = max(ans, max(dfs(st[i], ), dfs(en[i], )));

    for (int i = ; i <= m; ++i) {

        for (int j = st[i]; j <= en[i]; ++j) {

            int k = getlcp(j, j), l = j - k + , r = j + k - ;

            if (l != st[i] && r != en[i]) ans = max(ans, k *  - );

            else if (l == st[i] && r == en[i]) End();

            else if (l == st[i]) ans = max(ans, k *  -  + dfs(r + , ));

            else ans = max(ans, k *  -  + dfs(l - , ));

        }

        for (int j = st[i]; j < en[i]; ++j) {

            int k = getlcp(j + , j), l = j - k + , r = j + k; // r = j + 1 + k - 1 !!!

            if (l != st[i] && r != en[i]) ans = max(ans, k * );

            else if (l == st[i] && r == en[i]) End();

            else if (l == st[i]) ans = max(ans, k *  + dfs(r + , ));

            else ans = max(ans, k *  + dfs(l - , ));

        }

    }

    cout << ans;

    return ;

}