Educational Codeforces Round 163 (Rated for Div. 2)【思维+数学+前缀和】

原题链接：https://codeforces.com/problemset/problem/1948/D

题目描述

给定一个由小写字母和**问号 ? **组成的字符串 s，你可以将问号 ? 替换为任何小写字母。

替换后，你需要找到 s 中最长的重复子串。

一个长度为 2n 的字符串 t 是重复串，当且仅当对于所有 1≤i≤n，有 ti​=ti+n​。

输入格式

本题目含多组数据。

第一行，一个正整数 t，表示数据组数。

接下来每组数据仅包含一行，一个字符串 s。

输出格式

对于每组数据，输出一行一个非负整数，表示你得到的最长重复子串的长度。

如果这样的子串不存在，输出 0。

数据范围

对于 100% 的数据，保证 1≤t≤10^3,1≤∣s∣≤5×10^3​。

保证 ∑∣s∣≤5×10^3。

Translated by ShiRoZeTsu.

输入输出样例
输入 
4
zaabaabz
?????
code?????s
codeforces
输出 
6
4
10
0

解题思路：

这个题目我从洛谷上学习到了一个大佬一个非常巧妙的做法，我们不妨将各种字母映射成数字，其中?映射成0，a,b,c,...依次映射成1,2,3,...，我们可以暴力枚举所有偶数长度的区间，不妨设这个区间长度为2L，那么就需要判断每一个a[i]==a[i+L] (i表示这个区间前半部分的下标)是否成立，我们可以通过一个公式来判断是否相等，公式为(ai-aj)*(ai-aj)*ai*aj，只有当这个公式的值为0时俩个位置才可以相等，要使得这个等式为0，那么只需要(ai-aj)，ai，aj这三个中的某一个等于0即可，(ai-aj)表示俩个位置字符相同的情况，ai或者aj表示只要某个位置为?或者俩个位置都为？，那么我们可以通过编辑?使得俩个位置相同，由于我们刚好把?映射成了0，所以这个公式就用的非常的巧妙，至于这里的(ai-aj)为什么要乘俩次呢，这是因为我们不知道ai和aj谁大，所以可能会出现负数的情况对后续处理产生影响导致答案出错，所以这里的(ai-aj)乘俩次是为了避免出现负数，

那么俩个长度为n的串A,B匹配当且仅当(Ai-Bi)*(Ai-Bi)*Ai*Bi  (1<=i<=n)，我们枚举区间长度L，那么对于【l，l+L-1】=【l+L，l+L*2-1】就可以表示成f(i，i+L) (l<=i<=l+L-1)=0，我们可以预处理f数组的前缀和数组，然后暴力枚举每一个子区间，对于每一个子区间可以O(1)计算出答案，时间复杂度O(n^2)。

时间复杂度：O(n^2)。

空间复杂度：O(n^2)。

cpp代码如下：

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

using namespace std;
typedef long long LL;
const int N=5010;

int T,n;
int a[N],f[N][N],s[N][N];

void solve()
{
    string str;
    cin>>str;
    n=str.size();
    str=" "+str;
    for(int i=1;i<=n;i++)  //把每个字符映射成数字
    {
        if(str[i]=='?')a[i]=0;
        else a[i]=str[i]-'a'+1;
    }
    for(int i=1;i<=n;i++)  //根据公式计算f[i][j]
        for(int j=1;j<=n;j++)
            f[i][j]=(a[i]-a[j])*(a[i]-a[j])*a[i]*a[j];

    for(int len=1;len<=n;len++) //预处理f数组前缀和
        for(int l=1;l+len<=n;l++)
            s[len][l]=s[len][l-1]+f[l][l+len];
    
    int ans=0;
    for(int len=1;len<=n;len++)  //暴力枚举每一个子区间，更新答案
        for(int l=1;l+len*2-1<=n;l++)
            if(s[len][l+len-1]-s[len][l-1]==0)
                ans=max(ans,len*2);
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}