https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=596&page=show_problem&problem=4450

建好hash后,从做到右对称地扫一遍,中途记录匹配位置okpos,扫完后再判断一下

if ((len[0] & 1) || okpos < (len[0] >> 1) - 1) ++ans;
/*0.023s*/

const int mx_s_num = 1;
const int mx = 50005;
const ull B = 100000007ULL; /// 哈希基数,1e8 + 7

char s[mx_s_num][mx];
ull ha[mx_s_num][mx], bp[mx] = {1ULL};
int len[mx_s_num];

void init_hash(int s_num)
{
    int i, j;
    For(i, s_num) Forr(j, 1, len[i] + 1) ha[i][j] = ha[i][j - 1] * B + s[i][j];
    int n = *max_element(len, len + s_num);
    Forr(i, 1, n + 1) bp[i] = bp[i - 1] * B;
}

inline ull get_hash(ull *Ha, int pos, int l) /// 返回Ha[pos...pos+l-1]的值
{
    return Ha[pos + l - 1] - Ha[pos - 1] * bp[l];
}

int main()
{
    int t, cas = 0, i, j, ans, okpos;
    SI(t);
    while (t--)
    {
        printf("Case #%d: ", ++cas);
        scanf("%s", s[0] + 1);
        len[0] = strlen(s[0] + 1);
        init_hash(1);
        ans = 0;
        For(i, len[0] >> 1)
        {
            Forr(j, i, len[0] >> 1)
            {
                if (get_hash(ha[0], i + 1, j - i + 1) == get_hash(ha[0], len[0] - j, j - i + 1))
                {
                    ans += 2;
                    okpos = j;
                    break;
                }
            }
            i = j;
        }
        if ((len[0] & 1) || okpos < (len[0] >> 1) - 1) ++ans;
        PI(ans);
    }
    return 0;
}

Comments

comments powered by Disqus