{"id":174,"date":"2020-04-01T10:15:41","date_gmt":"2020-04-01T02:15:41","guid":{"rendered":"http:\/\/47.103.223.234:100\/?p=174"},"modified":"2020-04-15T21:57:48","modified_gmt":"2020-04-15T13:57:48","slug":"3-22-%e8%a1%a5%e9%a2%98-%e7%ac%ac%e5%85%ad%e6%ac%a1%e8%ae%ad%e7%bb%83","status":"publish","type":"post","link":"http:\/\/www.zyhcoding.club\/index.php\/2020\/04\/01\/3-22-%e8%a1%a5%e9%a2%98-%e7%ac%ac%e5%85%ad%e6%ac%a1%e8%ae%ad%e7%bb%83\/","title":{"rendered":"3-22 \u8865\u9898 \u7b2c\u516d\u6b21\u8bad\u7ec3"},"content":{"rendered":"

I. Match & Catch <\/a><\/h1>\n

\u9898\u610f\uff1a\u6c42\u4e24\u4e2a\u5b57\u7b26\u4e32\u4e2d\uff0c\u5728\u4e24\u4e32\u4e2d\u90fd\u53ea\u51fa\u73b0\u8fc7\u4e00\u6b21\u7684\u6700\u5c0f\u957f\u5ea6\u7684\u5b50\u4e32\uff0c\u8f93\u51fa\u8fd9\u4e2a\u6700\u5c0f\u957f\u5ea6\u3002
\n\u5206\u6790\uff1a\u628a\u4e24\u4e2a\u4e32\u4e2d\u95f4\u7528'#'\u8fde\u63a5\u8d77\u6765\uff0c\u521b\u5efa\u540e\u7f00\u6570\u7ec4\u548cHeight\u6570\u7ec4\uff0c\u7136\u540e\u626b\u63cfHeight\uff0c\u9700\u6ee1\u8db3\uff1a
\n1.Height[i-1]<Height[i]
\n2.Height[i+1]<Height[i]
\n3.\u5728\u6ee1\u8db31\uff0c2\u7684\u60c5\u51b5\u4e0b\uff0c\u8003\u8651\u7b54\u6848max{Height[i-1],Height[i+1]}+1.<\/p>\n

#include <cstdio>\n#include <cstring>\n#include <algorithm>\nusing namespace std;\nconst int maxn = 2e4+5;\ntypedef struct SA{\n   int SA[maxn],Rank[maxn],tp[maxn],tax[maxn],Height[maxn];\n   int n,m,n1;\n   char s[maxn];\n   void build(){\n      m = 130;\n      n = strlen(s+1);\n      GetSA(Rank,tp);\n      GetHeight();\n   }\n   void GetSA(int a[],int b[]);\n   void RSort(int a[],int b[]);\n   void GetHeight();\n   int check(int i);\n}SA;\nSA a;\nint ans;\nint main(){\n   scanf ("%s",a.s+1);  a.n1 = strlen(a.s+1);\n   a.s[a.n1+1] = '#';\n   scanf ("%s",a.s+a.n1+2);\n   a.build();\n   ans = maxn;\n   for (int i=1;i<=a.n;i++)\n      if (a.Height[i-1]<a.Height[i] && a.Height[i+1]<a.Height[i] && ((a.SA[i]<=a.n1 && a.SA[i-1]>=a.n1+2) || (a.SA[i-1]<=a.n1 && a.SA[i]>=a.n1+2)))\n         ans = min(ans,max(a.Height[i-1],a.Height[i+1])+1);\n   if (ans==maxn) printf ("-1\\n");\n   else   printf ("%d\\n",ans);\n   return 0;\n}\nvoid SA::GetHeight(){\n   int j,k=0;\n   for (int i=1;i<=n;i++){\n      if (k)   k--;\n      j = SA[Rank[i]-1];\n      while (s[i+k]==s[j+k])  k++;\n      Height[Rank[i]] = k;\n   }\n   return;\n}\nvoid SA::GetSA(int a[],int b[]){\n   for (int i=1;i<=n;i++)  a[i] = s[i],b[i] = i;\n   RSort(a,b);\n   int p=0,k=1;\n   for (;p!=n;k<<=1,m=p){\n      p = 0;\n      for (int i=n+1-k;i<=n;i++)   b[++p] = i;\n      for (int i=1;i<=n;i++)  if (SA[i]>k)   b[++p] = SA[i]-k;\n      RSort(a,b);    swap(a,b);\n      a[SA[1]] = p = 1;\n      for (int i=2;i<=n;i++)\n         a[SA[i]] = (b[SA[i]]==b[SA[i-1]] && b[SA[i]+k]==b[SA[i-1]+k])?p:++p;\n   }\n   for (int i=1;i<=n;i++)  Rank[SA[i]] = i;          \/\/\u8fd9\u4e00\u6b65\uff01\u56e0\u4e3aGetSA\u51fd\u6570\u53ea\u80fd\u4fdd\u8bc1SA\u6570\u7ec4\u5b8c\u5168\u6b63\u786e\uff0c\u5728\u8d4b\u503c\u5b8c\u6210\u540e\u6700\u597d\u5728\u7ed9Rank\u6570\u7ec4\u518d\u8d4b\u4e00\u6b21\u503c\n   return;\n}\nvoid SA::RSort(int a[],int b[]){\n   for (int i=1;i<=m;i++)  tax[i] = 0;\n   for (int i=1;i<=n;i++)  tax[a[b[i]]]++;\n   for (int i=1;i<=m;i++)  tax[i] += tax[i-1];\n   for (int i=n;i>=1;i--)  SA[tax[a[b[i]]]--] = b[i];\n   return;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
I. Match & Catch \u9898\u610f\uff1a\u6c42\u4e24\u4e2a\u5b57\u7b26\u4e32\u4e2d\uff0c\u5728\u4e24\u4e32\u4e2d\u90fd\u53ea\u51fa\u73b0\u8fc7\u4e00\u6b21\u7684\u6700\u5c0f\u957f\u5ea6\u7684\u5b50 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[18,27],"tags":[21,20],"_links":{"self":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/174"}],"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=174"}],"version-history":[{"count":2,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/174\/revisions"}],"predecessor-version":[{"id":176,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/posts\/174\/revisions\/176"}],"wp:attachment":[{"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/media?parent=174"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/categories?post=174"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.zyhcoding.club\/index.php\/wp-json\/wp\/v2\/tags?post=174"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}