這篇題解是建立在其他題解的基礎之上的。

若一個奇數長度的回文串沒有出現在串中，那麼比它長的奇數長度的回文串也不會出現。
偶數長度的回文串同理。

由此，只需要一次二分，在判斷mid是否滿足條件之前，順便先判斷一下mid+1（mid-1也可以）是否滿足條件（因為偶數+1==奇數，奇數+1==偶數）
即可。

核心代碼：

while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(check(mid+1)) l=mid+1;
        else
        if(check(mid)) l=mid;
        else r=mid-1;
    }

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1000010;

char s[N];
unsigned long long a[N],b[N],p[N];
int n,id=0;

bool check(int k)
{
    for(int i=1;i<=n-k+1;++i)
    {
        int r=i+k-1,l=i;
        if(a[r]-a[l-1]*p[r-l+1] == b[l]-b[r+1]*p[r-l+1]) return 1;
    }
    return 0;
}

void solve()
{
    n=strlen(s+1);
    for(int i=1;i<=n;++i)
    {
        a[i]=a[i-1]*131+(s[i]-'a'+1);
    }
    for(int i=n;i>=1;--i)
    {
        b[i]=b[i+1]*131+(s[i]-'a'+1);
    }
    int l=1,r=n;
    while(l<r)
    {
        int mid=(l+r+1)>>1;
        if(check(mid+1)) l=mid+1;
        else
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    cout<<"Case "<<++id<<':'<<' '<<ans<<'\n';
    return;
}

int main()
{
    p[0]=1;
    for(int i=1;i<=1000000;++i) p[i]=p[i-1]*131;
    scanf("%s",s+1);
    while(s[1]!='E')
    {
        solve();
        scanf("%s",s+1);
        memset(a,0,sizeof a);
        memset(b,0,sizeof b);
    }
}