{"id":257,"date":"2006-07-24T20:49:00","date_gmt":"2006-07-24T12:49:00","guid":{"rendered":"http:\/\/114415"},"modified":"2006-07-24T20:49:00","modified_gmt":"2006-07-24T12:49:00","slug":"kmp","status":"publish","type":"post","link":"https:\/\/www.yewen.us\/blog\/2006\/07\/kmp\/","title":{"rendered":"KMP"},"content":{"rendered":"<p>\u76f4\u63a5\u6284\u7684\u6b66\u5927\u674e\u6625\u8446\u8001\u5e08\u7684\u6570\u636e\u7ed3\u6784\u4e0a\u7684\u6539\u8fdbKMP<\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\/\/ return the first matching string2 in the string1\n#include &amp;lt;stdio.h&amp;gt;\n#include &amp;lt;string.h&amp;gt;\n#define MaxSize 1000\n\ntypedef struct\n{\n    char ch&#x5B;MaxSize];\n    int len;\n} SqString;\n\nvoid GetNextval(SqString t,int nextval&#x5B;])\n{\n    int j=0,k=-1;\n    nextval&#x5B;0]=-1;\n    while(j&amp;lt;t.len)\n    {\n        if((k==-1)||(t.ch&#x5B;j]==t.ch&#x5B;k]))\n        {\n            j++;\n            k++;\n            if(t.ch&#x5B;j]!=t.ch&#x5B;k]) nextval&#x5B;j]=k;\n            else nextval&#x5B;j]=nextval&#x5B;k];\n        }\n        else k=nextval&#x5B;k];\n    }\n}\n\nint KMP(SqString s,SqString t)\n{\n    int nextval&#x5B;MaxSize],i=0,j=0,v;\n    GetNextval(t,nextval);\n    while((i&amp;lt;s.len)&amp;&amp;(j&amp;lt;t.len))\n    {\n        if((j==-1)||(s.ch&#x5B;i]==t.ch&#x5B;j]))\n        {\n            i++;\n            j++;\n        }\n        else j=nextval&#x5B;j];\n    }\n    if(j&amp;gt;=t.len) v=i-t.len;\n    else v=-1;\n    return(v);\n}\n\nint main()\n{\n\/\/    freopen(&quot;kmp.in&quot;,&quot;r&quot;,stdin);\n\/\/    freopen(&quot;kmp.out&quot;,&quot;w&quot;,stdout);\n\n    SqString str1,str2;\n    gets(str1.ch);\n    str1.len=strlen(str1.ch);\n    gets(str2.ch);\n    str2.len=strlen(str2.ch);\n    printf(&quot;%dn&quot;,KMP(str1,str2));\n    return(0);\n}<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>\u76f4\u63a5\u6284\u7684\u6b66\u5927\u674e\u6625\u8446\u8001\u5e08\u7684\u6570\u636e\u7ed3\u6784\u4e0a\u7684\u6539\u8fdbKMP \/\/ return the first matching st [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[7,11],"tags":[93,315,435],"class_list":["post-257","post","type-post","status-publish","format-standard","hentry","category-tech-notes","category-contests","tag-kmp","tag-315","tag-435"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/s4aR5e-kmp","_links":{"self":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts\/257","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/comments?post=257"}],"version-history":[{"count":0,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/posts\/257\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/media?parent=257"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/categories?post=257"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.yewen.us\/blog\/wp-json\/wp\/v2\/tags?post=257"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}