MENU

Problem c

20181105A problem.pdf

哈希,只不过值不再与字符具体值有关,而只与该字符上一次出现位置有关。

感谢出题人不卡ull自然溢出

#include<cstdio>
#include<cstring>
#if __GNUC__
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#define inline __attribute__((always_inline))
#endif
char S[1000002], T[100002];
int n, m, last[1000002], head[1000002], next[1000002], pos;
unsigned long long bit[1000002] = { 1 }, ha, cur;
int main() {
#ifndef ONLINE_JUDGE
    freopen("c.in", "r", stdin), freopen("c.out", "w", stdout);
#endif
    scanf("%s%s", S + 1, T + 1), n = strlen(S + 1), m = strlen(T + 1);
    for (int i = 1; i <= n; ++i)bit[i] = bit[i - 1] * 19963;
    for (int i = m; i; --i)last[head[T[i]]] = i,head[T[i]] = i;
    for (int i = 1; i <= m; ++i)ha = last[i] ? ha * 19963 + i - last[i] : ha * 19963;
    memset(head, 0, sizeof head), memset(last, 0, sizeof last), memset(next, 0, sizeof next);
    for (int i = n; i; --i)last[head[S[i]]] = i, next[i] = head[S[i]], head[S[i]] = i;
    for (int i = 1; i <= m; ++i)cur = last[i] ? cur * 19963 + i - last[i] : cur * 19963;
    if (ha == cur)printf("%d\n", 1);
    for (int i = 2; i <= n - m + 1; ++i) {
        cur *= 19963, pos = i + m - 1;
        if (next[i - 1] < pos && next[i - 1])cur -= (next[i - 1] - i + 1) * bit[pos - next[i - 1]];
        if (last[pos] >= i)cur += pos - last[pos];
        if (ha == cur)printf("%d\n", i);
    }
}
Leave a Comment

captcha
请输入验证码