{"id":387,"date":"2017-03-15T20:01:00","date_gmt":"2017-03-15T12:01:00","guid":{"rendered":"http:\/\/kylelv.com\/?p=387"},"modified":"2017-12-28T14:52:01","modified_gmt":"2017-12-28T06:52:01","slug":"%e6%a8%a1%e6%9d%bf-%e5%90%8e%e7%bc%80%e6%95%b0%e7%bb%84","status":"publish","type":"post","link":"https:\/\/blog.kylelv.com\/?p=387","title":{"rendered":"\u6a21\u677f — \u540e\u7f00\u6570\u7ec4"},"content":{"rendered":"

\"\"<\/p>\n

#include<map>\r\n#include<cmath>\r\n#include<queue>\r\n#include<cstdio>\r\n#include<cstring>\r\n#include<iostream>\r\n#include<algorithm>\r\nusing namespace std;\r\n#define ll long long\r\n#define N 200010\r\nint n,v[N],sa1[N],rk1[N],sa2[N],rk2[N],ht[N];\r\nchar s[N];\r\nint *sa,*rk,*SA,*RK;\r\nint main()\r\n{\r\n    scanf(\"%d\",&n);\r\n    scanf(\"%s\",s+1);\r\n    rk=rk1;RK=rk2;sa=sa1;SA=sa2;\r\n    int i,k,j;\r\n    for(i=1;i<=n;i++) v[s[i]]++;\r\n    for(i=1;i<=200;i++) v[i]+=v[i-1];\r\n    for(i=n;i;i--) sa[v[s[i]]--]=i;\r\n    for(i=1;i<=n;i++) rk[sa[i]]=rk[sa[i-1]]+(s[sa[i]]!=s[sa[i-1]]);\r\n    for(k=1;k<=n;k<<=1)\r\n    {\r\n        for(i=1;i<=n;i++) v[rk[sa[i]]]=i;\r\n        for(i=n;i;i--) if(sa[i]>k) SA[v[rk[sa[i]-k]]--]=sa[i]-k;\r\n        for(i=n-k+1;i<=n;i++) SA[v[rk[i]]--]=i;\r\n        for(i=1;i<=n;i++) RK[SA[i]]=RK[SA[i-1]]+(rk[SA[i]]!=rk[SA[i-1]]||rk[SA[i]+k]!=rk[SA[i-1]+k]);\r\n        swap(sa,SA);swap(rk,RK);\r\n    }\r\n    k=0;\r\n    for(i=1;i<n;i++)\r\n    {\r\n        j=rk[i]-1;\r\n        while(s[sa[rk[i]]+k]==s[sa[j]+k]) k++;\r\n        ht[rk[i]]=k;\r\n        if(k) k--;\r\n    }\r\n    for(i=1;i<=n;i++) printf(\"%d \",sa[i]-1);\r\n    puts(\"\");\r\n    for(i=1;i<=n;i++) printf(\"%d \",rk[i]);\r\n    puts(\"\");\r\n    for(i=2;i<=n;i++) printf(\"%d \",ht[i]);\r\n    puts(\"\");\r\n    return 0;\r\n}<\/pre>\n
 <\/p>\n","protected":false},"excerpt":{"rendered":"
#include<map> #include<cmath> #include<q […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[36,19],"class_list":["post-387","post","type-post","status-publish","format-standard","hentry","category-bzoj","tag-36","tag-19"],"_links":{"self":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/387","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=387"}],"version-history":[{"count":1,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/387\/revisions"}],"predecessor-version":[{"id":388,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=\/wp\/v2\/posts\/387\/revisions\/388"}],"wp:attachment":[{"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=387"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=387"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.kylelv.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=387"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}