地址

https://hihocoder.com/problemset/problem/1721

题目

时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
愚人节那天，小Ho在小Hi的一个回文字符串中添加了一个字符。你能帮助小Hi找到被添加的是第几个字符吗？

输入
一个只包含小写字母的字符串S。
对于70%的数据，|S| ≤ 1000
对于100%的数据，|S| ≤ 500000
输出
输出一个整数K，表示删除第K(从1开始计数)个字符后，S会变成一个回文字符串。
数据保证有解。如果有多个解，输出其中K最小的。

样例输入

aaba

样例输出

1

思路

  1. 思维（"正解"）
因为题目保证有解，删除某一个字符后字符串回文。所以可以从两端向中间扫，出现不对称的字符时枚举下删除的是左右哪边的，注意如果是相连的相同字符时要删除靠左的
  1. hash（"邪教"）
    暴力从左到右枚举要删除的字符，利用hash比较删除后的是否相等。（写完就觉得不对劲，当时觉得这种hash不简单啊，怎么有人过的这么快！！！）

代码

//hash邪教代码
#include <bits/stdc++.h>

using namespace std;

#define MP make_pair
#define PB push_back
typedef long long LL;
typedef unsigned int UU;
typedef pair<int,int> PII;
const double eps=1e-8;
const double pi=acos(-1.0);
const int K=5e5+7;
const int mod=1e9+7;


UU hs1[K],hs2[K],p[K],base;
char ss[K];

UU get_hash1(int l,int r)
{
    if(l>r) return 0;
    return hs1[r]-hs1[l-1]*p[r-l+1];
}
UU get_hash2(int l,int r)
{
    if(l>r) return 0;
    return hs2[l]-hs2[r+1]*p[r-l+1];
}

int main(void)
{
    int ans=0;
    base=mod;
    scanf("%s",ss+1);
    p[0]=1;
    for(int i=1;i<K;i++)
        p[i]=p[i-1]*base;
    int len=strlen(ss+1),mid=(len-1)/2;
    for(int i=1;i<=len;i++)
        hs1[i]=hs1[i-1]*base+ss[i]-'a';
    for(int i=len;i;i--)
        hs2[i]=hs2[i+1]*base+ss[i]-'a';
    for(int i=1;i<=len;i++)
    if(len&1)
    {
        UU ta,tb;
        if(i<=mid)
        {
            ta=get_hash1(1,i-1)*p[mid-i+1]+get_hash1(i+1,mid+1);
            tb=get_hash2(mid+2,len);
        }
        else if(i==mid+1)
        {
            ta=get_hash1(1,mid);
            tb=get_hash2(mid+2,len);
        }
        else
        {
            ta=get_hash1(1,mid);
            tb=get_hash2(mid+2,i-1)+get_hash2(i+1,len)*p[i-1-mid-2+1];
        }
        if(ta==tb)
        {
            ans=i;break;
        }
    }
    else
    {
        UU ta,tb;
        if(i<=mid)
        {
            ta=get_hash1(1,i-1)*p[mid+1-i]+get_hash1(i+1,mid+1);
            tb=get_hash2(mid+3,len);
        }
        else if(i==mid+1||i==mid+2)
        {
            ta=get_hash1(1,mid);
            tb=get_hash2(mid+3,len);
        }
        else
        {
            ta=get_hash1(1,mid);
            tb=get_hash2(mid+2,i-1)+get_hash2(i+1,len)*p[i-1-mid-2+1];
        }
        if(ta==tb)
        {
            ans=i;break;
        }
    }
    printf("%d\n",ans);
    return 0;
}