\u5b57\u7b26\u4e32\u54c8\u5e0c\u7b97\u662f\u54c8\u5e0c\u7684\u4e00\u4e2a\u5c0f\u5206\u652f\u5427\u3002\u3002 hash[l..r] = hash[r] - hash[l-1]*pow(base,l-r+1)<\/p>\n<\/blockquote>\n \u8fd9\u4e2a\u4e00\u5b9a\u8981\u8bb0\u4f4f\uff0c\u719f\u7ec3\u3002 \u5b57\u7b26\u4e32HASH \u5b57\u7b26\u4e32\u54c8\u5e0c\u7b97\u662f\u54c8\u5e0c\u7684\u4e00\u4e2a\u5c0f\u5206\u652f\u5427\u3002\u3002 hash\uff0c\u53c8\u53eb\u6563\u5217\u8868\uff0c\u5373\u5bf9\u4e00\u4e2a\u6570\u636e(\u6574\u6570\uff0c\u6216\u5b57 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[10],"tags":[],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/74"}],"collection":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/comments?post=74"}],"version-history":[{"count":5,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/74\/revisions"}],"predecessor-version":[{"id":146,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/74\/revisions\/146"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=74"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=74"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=74"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}
\nhash\uff0c\u53c8\u53eb\u6563\u5217\u8868\uff0c\u5373\u5bf9\u4e00\u4e2a\u6570\u636e(\u6574\u6570\uff0c\u6216\u5b57\u7b26\u4e32\u7b49)\u901a\u8fc7\u6563\u5217\u51fd\u6570\u8f6c\u5316\u6210\u4e00\u4e2a\u4e0d\u6613\u91cd\u590d\u7684\uff0c\u53ef\u4ee5\u901a\u8fc7O(1)\u590d\u6742\u5ea6\u76f4\u63a5\u6765\u8bbf\u95ee\u7684\u6574\u6570(\u6216\u5176\u4ed6)\u3002
\n\u5b57\u7b26\u4e32hash\uff0c\u901a\u4fd7\u6765\u8bb2\uff0c\u5c31\u662f\u628a\u4e00\u4e2a\u5b57\u7b26\u4e32\u8f6c\u6362\u6210\u4e00\u4e2a\u6574\u6570\uff0c\u8fd9\u79cd\u8f6c\u6362\u662f\u4e00\u79cd\u4e00\u4e00\u6620\u5c04<\/strong>\u3002\u8f6c\u6362\u7684\u65b9\u5f0f\u5c31\u662f\u6563\u5217\u51fd\u6570\u3002\u7ade\u8d5b\u4e2d\u5e38\u7528\u7684\u6563\u5217\u51fd\u6570\u4e3a\u8fdb\u5236\u6cd5\u3002hash(i) = hash(i-1)*base+s[i]<\/code>\uff0c\u8fd9\u662f\u6700\u5e38\u89c1\u7684\uff0c\u5373\u4ee5\u8fdb\u5236\u7684\u65b9\u5f0f\u5bf9\u4e00\u4e2a\u5b57\u7b26\u4e32\u8fdb\u884chash\uff0c\u5176\u4e2dbase\u4e3a\u8fdb\u5236\u7684\u57fa\uff0c\u8fd9\u4e2a\u6570\u901a\u5e38\u5f88\u5927\uff0c\u56e0\u6b64\u4e00\u822c\u5bf9\u4e00\u4e2a\u5927\u8d28\u6570\u53d6\u6a21\u6765\u5b58\u50a8\u3002\u5f53\u4e24\u4e2a\u5b57\u7b26\u4e32\u7684\u54c8\u5e0c\u503c\u76f8\u540c\u65f6\uff0c\u5c31\u53d1\u751f\u4e86\u6563\u5217\u51b2\u7a81\u3002
\n\u4e3a\u4e86\u89e3\u51b3\u8fd9\u79cd\u60c5\u51b5\uff0c\u6211\u4eec\u5c3d\u53ef\u80fd\u7684\u4f7f\u6563\u5217\u51fd\u6570\u4e3a\u4e00\u4e00\u6620\u5c04\uff0c\u901a\u5e38\uff0c\u57fa\u6570base\u53d6\u8d28\u6570131\uff0c\u6216\u80051331\uff0c\u6a21\u6570\u53d6\u4e00\u5927\u8d28\u65701e9+7,1e9+7\u7b49\uff0c\u4e5f\u53ef\u4ee5\u76f4\u63a5\u4f7f\u7528ull\u81ea\u7136\u6ea2\u51fa(\u8865\u5145\uff1aunsigned\u7c7b\u578b\u6574\u6570\uff0c\u5f53\u6570\u503c\u5927\u5c0f\u8d85\u51fa\u6570\u636e\u7c7b\u578b\u8303\u56f4\u65f6\uff0c\u6700\u7ec8\u7ed3\u679c\u4e3a\u5b9e\u9645\u6570\u503c\u5bf9\u8be5\u6570\u636e\u7c7b\u578b\u7684\u6700\u5927\u6570\u53d6\u6a21\u7684\u7ed3\u679c\uff0c\u5373ull\u6ea2\u51fa\u540e\uff0c\u7ed3\u679c\u662f\u5bf92^{64}<\/code>\u53d6\u6a21\u7684\u503c)\u3002\u8fd9\u662f\u5355hash\u65b9\u6cd5\u3002
\n\u53cchash\u5176\u5b9e\u5c31\u662f\u53d6\u4e24\u4e2abase\uff0c\u53d6\u4e24\u4e2amod\uff0c\u7136\u540e\u5f97\u5230\u4e24\u4e2ahash\u503c\uff0c\u7528\u8fd9\u503c\u4e2ahash\u503c\u7ec4\u6210\u7684\u4e00\u4e2a\u4e8c\u5143\u7ec4\u6765\u4f5c\u4e3a\u8fd9\u4e2a\u5b57\u7b26\u4e32\u7684hash\uff0c\u8fd9\u79cd\u65b9\u6cd5\u57fa\u672c\u4e0d\u4f1a\u51fa\u9519\u3002
\n\u83b7\u53d6\u5b50\u4e32l~r\u7684hash\uff1a<\/p>\n\n
\n\u4e0b\u9762\u662fN*M\u4e8c\u7ef4\u77e9\u9635\u5339\u914d\u7684\u6a21\u677f<\/p>\n#include <cstdio>\nusing namespace std;\ntypedef unsigned long long ull;\nconst ull maxn = 1005,base1 = 131,base2 = 1331;\null N,M,X,Y;\nchar s[maxn][maxn],t[105][105];\null w1[maxn][maxn],temp[maxn][maxn],w2[105][105],pow_mod1[105],pow_mod2[105];\nvoid init();\nint main(){\n init();\n int T,ans;\n scanf ("%d",&T);\n while (T--){\n ans = 0;\n scanf ("%d %d",&N,&M);\n if (N && M)\n for (int i=1;i<=N;i++) scanf ("%s",s[i]+1);\n scanf ("%d %d",&X,&Y);\n if (X==0 || Y==0 || N==0 || M==0){\n printf("0\\n");\n continue;\n }\n for (int i=1;i<=X;i++) scanf ("%s",t[i]+1);\n if (X>N || Y>M){\n printf("0\\n");\n continue;\n }\n for (int i=1;i<=N;i++){\n for (int j=1;j<=M;j++) w1[i][j] = w1[i][j-1]*base1+s[i][j];\n for (int j=1;j<=M-Y+1;j++) temp[i][j] = w1[i][j+Y-1]-w1[i][j-1]*pow_mod1[Y];\n }\n for (int j=1;j<=M-Y+1;j++){\n for (int i=1;i<=N;i++) temp[i][j] = temp[i-1][j]*base2+temp[i][j];\n for (int i=1;i<=N-X+1;i++) w1[i][j] = temp[i+X-1][j] - temp[i-1][j]*pow_mod2[X];\n }\n for (int i=1;i<=X;i++){\n for (int j=1;j<=Y;j++) w2[i][j] = w2[i][j-1]*base1+t[i][j];\n w2[i][Y] = w2[i-1][Y]*base2+w2[i][Y];\n }\n for (int i=1;i<=N-X+1;i++) for (int j=1;j<=M-Y+1;j++)\n if (w1[i][j]==w2[X][Y]) ans++;\n printf("%d\\n",ans);\n }\n return 0;\n}\nvoid init(){\n pow_mod1[1] = base1,pow_mod2[1] = base2;\n for (int i=2;i<=100;i++){\n pow_mod1[i] = pow_mod1[i-1]*base1;\n pow_mod2[i] = pow_mod2[i-1]*base2;\n }\n return;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"