{"id":123,"date":"2023-04-13T20:44:00","date_gmt":"2023-04-13T12:44:00","guid":{"rendered":"https:\/\/solost.cn\/?p=123"},"modified":"2023-04-13T21:27:10","modified_gmt":"2023-04-13T13:27:10","slug":"230","status":"publish","type":"post","link":"https:\/\/solost.cn\/?p=123","title":{"rendered":"\u5b57\u7b26\u4e32\u54c8\u5e0c"},"content":{"rendered":"

\u6838\u5fc3\u601d\u60f3<\/h2>\n

\u5c06\u5b57\u7b26\u4e32\u770b\u6210P\u8fdb\u5236\u6570\uff0cP\u7684\u7ecf\u9a8c\u503c\u662f131\u621613331\uff0c\u53d6\u8fd9\u4e24\u4e2a\u503c\u7684\u51b2\u7a81\u6982\u7387\u4f4e
\u5c0f\u6280\u5de7\uff1a\u53d6\u6a21\u7684\u6570\u75282^64\uff0c\u8fd9\u6837\u76f4\u63a5\u7528unsigned long long\u5b58\u50a8\uff0c\u6ea2\u51fa\u7684\u7ed3\u679c\u5c31\u662f\u53d6\u6a21\u7684\u7ed3\u679c<\/p>\n

\u6a21\u677f<\/h2>\n
typedef unsigned long long ULL;\nULL h[N], p[N]; \/\/ h[k]\u5b58\u50a8\u5b57\u7b26\u4e32\u524dk\u4e2a\u5b57\u6bcd\u7684\u54c8\u5e0c\u503c, p[k]\u5b58\u50a8 P^k mod 2^64\n\n\/\/ \u521d\u59cb\u5316\np[0] = 1;\nfor (int i = 1; i <= n; i ++ )\n{\n    h[i] = h[i - 1] * P + str[i];\n    p[i] = p[i - 1] * P;\n}\n\n\/\/ \u8ba1\u7b97\u5b50\u4e32 str[l ~ r] \u7684\u54c8\u5e0c\u503c\nULL get(int l, int r)\n{\n    return h[r] - h[l - 1] * p[r - l + 1];\n}<\/code><\/pre>\n
\u6c42\u4e00\u4e2a\u6570\u7684hash\u503c<\/h2>\n
\u6c42\u4e00\u4e2a\u6570\u7684hash\u503c\u5176\u5b9e\u5c31\u662f\u628a\u8fd9\u4e2a\u6570\u5b57\u8f6c\u6362\u6210p\u8fdb\u5236\uff0c\u8f6c\u6362\u540e\u7684\u6570\u5c31\u662fhash\u503c<\/p>\n
\u4f8b\u9898<\/h2>\n
\u9898\u9762<\/h3>\n
\"image.png\"<\/p>\n
\u9898\u76ee\u94fe\u63a5<\/h3>\n
\u94fe\u63a5<\/a><\/p>\n
\u9898\u89e3<\/h3>\n
#include <map>\n#include <set>\n#include <cmath>\n#include <queue>\n#include <stack>\n#include <utility>\n#include <vector>\n#include <bitset>\n#include <cstdio>\n#include <cstdlib>\n#include <cstring>\n#include <fstream>\n#include <iostream>\n#include <algorithm>\n#include <unordered_map>\n#include <unordered_set>\n\nusing namespace std;\n#define x first\n#define y second\n#define endl '\\n'\n#define IOS                       \\\n    ios_base::sync_with_stdio(0); \\\n    cin.tie(0);                   \\\n    cout.tie(0);\ntypedef long long ll;\ntypedef pair<ll, ll> pll;\ntypedef pair<int, int> pii;\ntypedef unsigned long long ull;\n\nconst int INF = 0x3f3f3f3f, mod = 1000000007, P = 131;\nconst int N = 2e5 + 10;\n\null h[N], p[N];\n\null get(int l, int r){\n    return h[r] - h[l - 1] * p[r - l + 1];\n    \/*\n    \u533a\u95f4\u548c\u516c\u5f0f\u7684\u7406\u89e3: ABCDE \u4e0e ABC \u7684\u524d\u4e09\u4e2a\u5b57\u7b26\u503c\u662f\u4e00\u6837\uff0c\u53ea\u5dee\u4e24\u4f4d\uff0c\n    \u4e58\u4e0aP\u7684\u4e8c\u6b21\u65b9\u628a ABC \u53d8\u4e3a ABC00\uff0c\u518d\u7528 ABCDE - ABC00 \u5f97\u5230 DE \u7684\u54c8\u5e0c\u503c\u3002\n    \u76f8\u5f53\u4e8e\u6c42abc\u7684\u54c8\u5e0c\u503c\uff0c\u628aabc\u5f80\u540e\u9876r - l + 1\u4f4d\uff0c\u7136\u540e\u76f8\u51cf\u5f97\u5230\u7684\u5c31\u662fhash\u503c\n    *\/\n}\n\nvoid solve()\n{\n    int n, m;\n    cin >> n >> m;\n    string s;\n    cin >> s;\n    s = ' ' + s;\n    p[0] = 1;\n    for(int i = 1; i <= n; i++){\n        h[i] = h[i - 1] * P + s[i];\n        p[i] = p[i - 1] * P;\n    }\n    while(m--){\n        int l1, r1, l2, r2;\n        cin >> l1 >> r1 >> l2 >> r2;\n        if(get(l1, r1) == get(l2, r2)){\n            cout << "Yes\\n";\n        }\n        else{\n            cout << "No\\n";\n        }\n    }\n}\nint main()\n{\n    \/\/ IOS;\n    int t = 1;\n    \/\/ cin >> t;\n    while (t--) {\n        solve();\n    }\n    return 0;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u6838\u5fc3\u601d\u60f3 \u5c06\u5b57\u7b26\u4e32\u770b\u6210P\u8fdb\u5236\u6570\uff0cP\u7684\u7ecf\u9a8c\u503c\u662f131\u621613331\uff0c\u53d6\u8fd9\u4e24\u4e2a\u503c\u7684\u51b2\u7a81\u6982\u7387\u4f4e\u5c0f\u6280\u5de7\uff1a\u53d6\u6a21\u7684\u6570\u75282^64\uff0c\u8fd9\u6837\u76f4\u63a5\u7528unsigned long long\u5b58\u50a8\uff0c\u6ea2\u51fa\u7684\u7ed3\u679c\u5c31\u662f\u53d6\u6a21\u7684\u7ed3\u679c \u6a21\u677f typedef unsigned long long ULL; ULL h[N], p[N]; \/\/ h[k]\u5b58\u50a8\u5b57\u7b26\u4e32\u524dk\u4e2a\u5b57\u6bcd\u7684\u54c8\u5e0c\u503c, p[k]\u5b58\u50a8 P^k mod 2^64 \/\/ \u521d\u59cb\u5316 p[0] = 1; for (int i = 1; i <= n; i ++ ) { h[i] = h[i - 1] * P + str[i]; p[i] = p[i - 1] * P; } \/\/ \u8ba1\u7b97\u5b50\u4e32 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[72],"tags":[23],"class_list":["post-123","post","type-post","status-publish","format-standard","hentry","category-acm","tag-hash"],"_links":{"self":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/123","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=123"}],"version-history":[{"count":0,"href":"https:\/\/solost.cn\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions"}],"wp:attachment":[{"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=123"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/solost.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}