Checking the Text 文本校对

[POJ 2758] && [BZOJ 2258] && [NFLSOJ - 文本校对]

题面

描述

为了给Wind买生日礼物，Jiajia不得不找了一份检查文本的工作。这份工作很无聊：给你一段文本
要求比对从文本中某两个位置开始能匹配的最大长度是多少。但比无聊更糟糕的是，Jiajia的经理
还可能往文本里面插入一些字符。
Jiajia想用一个程序来解决这些繁琐的工作。这个程序的速度要足够快，因为Wind的生日就快要到了
Jiajia必须赚到足够多的钱，也就是处理足够多的文本。

输入

输入文件第一行是原始文本。
输入文件第二行是操作数n。此后n行，每行描述一条命令，命令有两种形式：
I ch p：表示将一个字符ch插入到当前文本的第p个字符之前，如果p大于当前文本长度则表示插入到当前文本末尾；
Q i j：表示询问当前文本从原始文本的第i个和第j个字符现在所在的位置开始能匹配的字符是多少。
你可以认为文本初始长度不超过50000，I命令最多200条，Q命令最多20000条。

输出

对于每条Q命令输出一行，为最长匹配长度。

样例输入

abaab
5
Q 1 2
Q 1 3
I a 2
Q 1 2
Q 1 3

样例输出

0
1
0
3

Solution

对于操作 1 ：由于插入的操作量较少，可以直接暴力插入
对于操作 2 ：实际是求 LCP ,那么满足二分性质:存在一分界点,使得分界点前字符都相匹配,分界点后都不匹配。因而二分找位置即可。
对于字符，可以转为哈希值储存，以便于后续操作，同时推导出区间哈希公式：h[l ~ r] = h[r] - h[l - 1] * pw[r - l + 1]. 其中 pw 为对应数乘过 P(进制数) 的次数。
num[i] 记录 i 在原序列中的位置, p[i] 记录 i 在受多次插入字符影响而改变后的位置。

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

#define ull unsigned long long

using namespace std;

const int N = 5e4 + 210, P = 13331;
int n, len;
char str[N];
int p[N], num[N], a[N];
ull pw[N];
ull h[N];

inline ull check (ull l, ull r)
{
    return h[r] - h[l - 1] * pw[r - l + 1];
}

signed main()
{
    scanf ("%s", str + 1);
    len = strlen (str + 1);
    
    pw[0] = 1;
    for (int i = 1;i <= 50000;i ++ )
    {
        pw[i] = pw[i - 1] * P;
    }
    
    for (int i = 1;i <= len;i ++ )
    {
        p[i] = i, num[i] = i;
        a[i] = str[i] - 'a' + 1;
        h[i] = h[i - 1] * P + a[i];
    }
    
    scanf ("%d", &n);
    
    while (n -- )
    {
        char ch;
        int x, y;
        
        cin >> ch;
        if (ch == 'Q')
        {
            scanf ("%d%d", &x, &y);
            
            x = p[x], y = p[y];
            
            int l = 0, r = len - max (x, y) + 2;
            while (l + 1 < r)
            {
                int mid = (l + r) >> 1;
                if (check (x, x + mid - 1) == check (y, y + mid - 1))
                {
                    l = mid;
                }
                else
                {
                    r = mid;
                }
            }
            
            printf ("%d\n", l);
        }
        else
        {
            scanf (" %c %d", &ch, &x);
            if (x > len)
            {
                a[ ++ len] = ch - 'a' + 1;
            }
            else
            {
                len ++ ;
                for (int i = len;i > x;i -- )
                {
                    a[i] = a[i - 1];
                    num[i] = num[i - 1];
                    p[num[i]] ++ ;
                }
                
                a[x] = ch - 'a' + 1;
                num[x] = 0;
            }
            
            for (int i = x;i <= len;i ++ )
            {
                h[i] = h[i - 1] * P + a[i];
            }
        }
    }
    
    return 0;
}

ps:很菜的孩子写的个人理解,如有错误感谢指正!