字串雜湊On求最長迴文子串

模板題連結 AcWing139. 迴文子串的最大長度

眾所周知，manacher可以On求最長迴文子串 ，但是神奇的字串hash也可以做到求最長迴文串。

步驟：

1. 預處理字串，類似於manacher，每兩個字元中間插入‘#’，因為這樣才能列舉中心。
2. 預處理正雜湊和逆雜湊，如果正雜湊[l,r]==逆雜湊[l,r]，說明兩個字串相同。
3. 列舉迴文中心，二分求迴文半徑。

可以看出，時間複雜度是$O(nlogn)$，程式碼如下：

unsigned long long order1[2000100], order2[2000100];
unsigned long long pwd[2000100], base = 13331;
char s[2000100];
char s2[2000100];
int ct = 1;
bool check(int pos, int r)
{
    unsigned long long temp1 = order1[pos + r - 1] - order1[pos - 1] * pwd[r];
    unsigned long long temp2 = order2[pos - r + 1] - order2[pos + 1] * pwd[r];
    if (temp1 == temp2)
        return 1;
    return 0;
}
int main()
{
    pwd[0] = 1;
    for (int i = 1; i <= 1000000; i++)
        pwd[i] = pwd[i - 1] * base;
    int CASE = 1;
    while (~scanf("%s", s))
    {
        if (!strcmp(s, "END"))
            break;
        printf("Case %d: ", CASE++);
        int len = strlen(s);
        ct = 1;
        s2[ct++] = '#';
        for (int i = 0; i < len; i++)
        {
            s2[ct++] = s[i];
            s2[ct++] = '#';
        }
        len = ct - 1;

        order1[0] = order2[len + 1] = 0;
        for (int i = 1; i <= len; i++)
            order1[i] = order1[i - 1] * base + s2[i];
        for (int i = len; i >= 1; i--)
            order2[i] = order2[i + 1] * base + s2[i];
        int pos = 1, maxx = 0;

        for (int i = 1; i <= len; i++)
        {
            int l = 1, r = min(len - i + 1, i);
            while (l <= r)
            {
                int mid = l + r >> 1;
                if (check(i, mid))
                {
                    l = mid + 1;
                    maxx = max(maxx, mid - 1);
                }
                else
                    r = mid - 1;
            }
        }
        printf("%d\n", maxx);
    }
    return 0;
}

這**博主怎麼騙人啊，不是On複雜度嗎。

其實，不需要二分，直接記錄當前最長半徑，下次列舉直接使用從之前的最大半徑開始即可。

$O(n)$程式碼：

unsigned long long order1[2000100], order2[2000100];
unsigned long long pwd[2000100], base = 13331;
char s[2000100];
char s2[2000100];
int ct = 1;

unsigned long long gethash1(int l, int r)
{
    return order1[r] - order1[l - 1] * pwd[r - l + 1];
}
unsigned long long gethash2(int l, int r)
{
    return order2[l] - order2[r + 1] * pwd[r - l + 1];
}
int main()
{
    pwd[0] = 1;
    for (int i = 1; i <= 1000000; i++)
        pwd[i] = pwd[i - 1] * base;
    int CASE = 1;
    while (~scanf("%s", s))
    {
        if (!strcmp(s, "END"))
            break;
        printf("Case %d: ", CASE++);
        int len = strlen(s);
        ct = 1;
        s2[ct++] = '#';
        for (int i = 0; i < len; i++)
        {
            s2[ct++] = s[i];
            s2[ct++] = '#';
        }
        len = ct - 1;

        order1[0] = order2[len + 1] = 0;
        for (int i = 1; i <= len; i++) //正雜湊
            order1[i] = order1[i - 1] * base + s2[i];
        for (int i = len; i >= 1; i--) //逆雜湊
            order2[i] = order2[i + 1] * base + s2[i];

        int maxx = 0;
        for (int i = 1; i <= len; i++) //On求最長迴文子串
            while (i - maxx >= 1 && i + maxx <= len &&
                   gethash1(i - maxx, i + maxx) == gethash2(i - maxx, i + maxx))
                maxx++;

        printf("%d\n", maxx - 1);
    }
    return 0;
}