[coci2015-2016 coii] Palinilap【字符串 哈希】
阅读原文时间:2023年07月13日阅读:3

传送门:http://www.hsin.hr/coci/archive/2015_2016/

进去之后点底下的那个。顺带说一句,题目既不是一个英文单词,也不是克罗地亚单词,估计只是从回文串的英文单词palindrome取出前5个字母,再反向复制一遍,造了一个回文串单词。

官方题解说的有点短小精悍,总之步骤就是这样子的:先统计一下原始串有几个回文子串。注意这里我用的是哈希+二分求的,manacher不知道可不可以,可能会很麻烦,因为后面的步骤是奇偶分开讨论的,这里仅仅考虑回文子串的长度为奇数的情况,偶数情况同理,只有一个地方有一点点小差别,后面我会标注(这个小差别葬送了我至少5个小时的调试时间!)。

先解释一下,后文的a[]数组就是我存取原串的数组。

那么现在只需求出,对于每个位置,这个位置的字母如果换成另外一个,会减少以及增加几个回文子串。先考虑增加几个。开一个数组inc[100005][26],inc[i][j]表示第i个位置的字母换成字母j会新增几个回文子串。该怎么计算呢?假设当前正在计算以位置i为中心,可以向两边扩展的长度,按照哈希+二分的算法,当你的left == right时(left和right表示的是二分的上界以及下界),此时是能扩展的最大长度(在我的程序里面,这个长度是包括了第i个字符的,也就是说以i为中心的最长回文子串的左边界是i - left + 1,右边界是i + right - 1),再扩展一点点就会遇到字符不匹配的情况,因此我们就让这两个字符匹配,对应了题目要求的只能修改一个字符。这两个字符匹配后,就再哈希+二分一次,看一下能再匹配几个字符,假设包括修改的那个字符,一共多匹配了x个,那么就:

inc[i - left][a[i + left] - 'a'] += x;  //表示把第(i - left)位置的字符改成第(i + left)字符会新增x个回文子串

inc[i + left][a[i - left] - 'a'] += x;  //类似以上

现在就要求对于每个位置,如果该位置替换一个字母会导致减少几个回文子串,开个数组dec[100005]。举个例子,这里有一个回文串:

a b c d e f e d c b a

假设我们把第三位的'c'换掉,随便换成什么,比如说换成g:

a b g d e f e d c b a

那么这就减少了3个以'f'为中心的回文子串。因此对于一个当前位置i,以他为中心的最长扩展长度为left(就是哈希+二分的结果),如果位置j被替换成其它任意一个串:

①,如果i - left + 1 <= j <= i - 1,那么会减少(j - (i - left))个以位置i为中心的回文子串。所以要dec[j] += (j - (i - left)),代表j位置换了字符,会导致多减少了(j - (i - left))个回文子串。

②,如果i + 1 <= j <= i + left - 1,那么会减少((i + left) - j)个以位置i为中心的回文子串。

这里只考虑第①种情况,第②种同理。显然,不可能按照刚刚说的对于每个位置j都加一遍,这样子效率明显应对不过来。所以,对于当前位置i,(i - left)是一个定值,也就是说(j - (i - left))这个值,随着j的增大而增大,更具体的,是对dec数组的某一段加一个等差数列,比如刚刚那个例子,a b g d e f e d c b a, dec[1] += 1, dec[2] += 2, dec[3] += 3。也就是说,现在的任务就是要快速对一个数组(这里是dec[]数组)的某个区间加上一个以1为首项,1为公差的等差数列。类似差分数组,我们先构建两个辅助数组c1[100005], c2[100005]。

对于“dec[1] += 1, dec[2] += 2, dec[3] += 3”这个操作,我们可以先让区间[1, 3]每项各加1,再让区间[2, 3]各加1,再让区间[3, 3]各加1。按照差分数组的思想,应该要这么做:

1    2    3    4    5

c2     +1             -1

c2          +1        -1

c2               +1   -1

然后再对c2数组求一次前缀和,存到dec里,那么就得到了dec[]的所有值。可是这样一来还不如刚刚的直接操作dec数组快,所以还需要借用一下c1数组。观察到c2数组里[1, 3]的位置都加了一次1,而4位置减了3,因此我们构建的c1数组,其前缀和就是c2数组!类比刚刚的思想,应该这么做:

1    2    3    4    5

c1     +1             -1

c1                    -3   +3

对c1数组求前缀和,保存在c2里,再对c2数组求前缀和,保存在dec里,便得出了dec的所有的值,具体看代码里的incc与decc函数。

之前说回文子串如果有偶数长度,有点小特殊,这就特殊在,如果是奇数长度,那么中心字符被换成了另外一个字符,并不会影响以这个中心字符为中心的回文子串数量,而如果是偶数长度,中心字符有两个,比如a b c c b a,中心字符就是两个c,此时替换任意一个中心字符,会影响到以这两个中心字符为中心的回文子串数量,千万注意!最后,哈希的mod如果让他自然溢出unsigned long long,会被卡一个点,我与std用的都是1e9+7。

#include
#include
#include

const int maxn = 100005;
const long long base = 131, mod = 1000000007;

int n, mx, mx_id;
long long inc[maxn][26], dec[maxn], c1[maxn], c2[maxn], ori_ans, delta_ans;
char a[maxn];
long long poww[maxn], hash1[maxn], hash2[maxn];

inline long long get_hash1(int left, int right) {
return ((hash1[right] - hash1[left - 1] * poww[right - left + 1]) % mod + mod) % mod;
}
inline long long get_hash2(int left, int right) {
return ((hash2[left] - hash2[right + 1] * poww[right - left + 1]) % mod + mod) % mod;
}
inline void incc(int left, int right) {
++c1[left];
c1[right + 1] -= (right - left + 2);
c1[right + 2] += (right - left + 1);
}
inline void decc(int left, int right) {
++c1[right + 2];
c1[left] += (right - left + 1);
c1[left + 1] -= (right - left + 2);
}

int main(void) {
freopen("palinilap.in", "r", stdin);
freopen("palinilap.out", "w", stdout);
scanf("%s", a + 1);
n = strlen(a + 1);
a[0] = '$';

poww\[0\] = 1ull;  
for (int i = 1; i <= n; ++i) {  
    poww\[i\] = poww\[i - 1\] \* base % mod;  
}  
for (int i = 1; i <= n; ++i) {  
    hash1\[i\] = (hash1\[i - 1\] \* base + a\[i\]) % mod;  
}  
for (int i = n; i; --i) {  
    hash2\[i\] = (hash2\[i + 1\] \* base + a\[i\]) % mod;  
}

int left, right, mid;  
for (int i = 1; i < n; ++i) {  
    for (int j = i; j < i + 2; ++j) {  
        left = 0;  
        right = std::min(i, n - j + 1);  
        while (left < right) {  
            mid = (left + right + 1) >> 1;  
            if (get\_hash1(i - mid + 1, i) == get\_hash2(j, j + mid - 1)) {  
                left = mid;  
            }  
            else {  
                right = mid - 1;  
            }  
        }  
        ori\_ans += (long long)left;

        if (left > 0) {  
            if (i == j) {  
                incc(i - left + 1, i - 1);  
                decc(j + 1, j + left - 1);  
            }  
            else {  
                incc(i - left + 1, i);  
                decc(j, j + left - 1);  
            }  
        }

        if (i - left <= 0 || j + left > n) {  
            continue;  
        }  
        long long & tem1 = inc\[i - left\]\[a\[j + left\] - 'a'\];  
        long long & tem2 = inc\[j + left\]\[a\[i - left\] - 'a'\];  
        int ori\_left = left;  
        right = std::min(i - left - 1, n - j - left);  
        left = 0;  
        while (left < right) {  
            mid = (left + right + 1) >> 1;  
            if (get\_hash1(i - ori\_left - mid, i - ori\_left - 1) == get\_hash2(j + ori\_left + 1, j + ori\_left + mid)) {  
                left = mid;  
            }  
            else {  
                right = mid - 1;  
            }  
        }  
        tem1 += left + 1;  
        tem2 += left + 1;  
    }  
}

for (int i = 1; i <= n; ++i) {  
    c2\[i\] = c2\[i - 1\] + c1\[i\];  
    dec\[i\] = dec\[i - 1\] + c2\[i\];  
}

for (int i = 1; i <= n; ++i) {  
    for (int j = 0; j < 26; ++j) {  
        if (j == a\[i\] - 'a') {  
            continue;  
        }  
        delta\_ans = std::max(delta\_ans, inc\[i\]\[j\] - dec\[i\]);  
    }  
}  
++ori\_ans;  
printf("%I64d\\n", ori\_ans + delta\_ans);  
return 0;  

}