题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1355
离线版题目：http://paste.ubuntu.com/17890900/
这一道题目，让我有一种自杀的冲动QAQ
先是想：嗯，SA的话O（nlogn）应该能过，于是开开心心去写SA
然而都快写完了，突然发现：WTF！被卡内存了
于是想KMP，总算回忆起那个神奇的结论，于是又写KMP，结果还写挂啦QAQ
不说了，说的了都是泪QAQ
本来是一道水题，结果做了俩小时QAQ
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 2000000+9;
char pat[MAXN];
int nxt[MAXN],n;
int main(){
scanf("%d%s",&n,pat+1);
for (int i=2,j=0;i<=n;i++){
while (j&&pat[j+1] != pat[i]) j=nxt[j];
if (pat[j+1]==pat[i]) j++;
nxt[i] = j;
}
printf("%d\n",n-nxt[n]);
return 0;
}
好吧，我承认这题还是比较好玩的。以前以为Kmp的那个结论只有整除的时候才能用。
刚刚证了证发现非整除也可以用QAQ
另外%这位大神，用hash把内存给省下去了：http://blog.csdn.net/wzq_qwq/article/details/49005295
我hash果然还是弱得完全没法用
961690 326566Not long noticed concerning your web website and are still already reading along. I assumed ill leave my initial comment. i do not verify what saying except that Ive enjoyed reading. Nice weblog. ill be bookmarking maintain visiting this internet web site genuinely normally. 217737
61507 707651I gotta bookmark this web site it seems extremely useful . 11216
568829 607581This sort of in search of get the enhancements produced on this particular lifestyle and diet, begin your L . a . Shifting the pounds diet answer is really a huge procedure into accesing which generally hope. weight loss 102757
776105 422242I must test with you here. Which is not 1 thing I normally do! I enjoy studying a submit that will make folks think. Also, thanks for permitting me to comment! 789457
649208 747352i was just surfing along and came upon your weblog. just wanted to say very good job and this post truly helped me. 929951
871284 717368I want to start a weblog but would like to own the domain. Any concepts how to go about this?. 541353
834327 881568Great work! That is the type of info that are supposed to be shared across the net. 444935
534967 81519Today, I went to the beach front with my kids. I found a sea shell and gave it to my 4 year old daughter and said “You can hear the ocean if you put this to your ear.” She put the shell to her ear and screamed. There was a hermit crab inside and it pinched her ear. She never wants to go back! LoL I know this is totally off topic but I had to tell someone! 596765
757478 65047I came towards the exact conclusion as well some time ago. Great write-up and I will probably be confident to look back later for a lot more news. 481975
706557 173896 I discovered your blog website on google and check a couple of of your early posts. Continue to maintain up the extremely excellent operate. I just additional up your RSS feed to my MSN News Reader. Seeking forward to reading more from you later on! 106017
15712 593855Hey there, I think your site might be having browser compatibility issues. When I look at your blog in Chrome, it looks fine but when opening in Internet Explorer, it has some overlapping. I just wanted to give you a quick heads up! Other then that, superb blog! 929917
212705 304606Hello! Good post! Please do keep us posted when we can see a follow up! 322066
Regards for this wonderful post, I am glad I noticed this web site on yahoo.
Enjoyed studying this, very good stuff, appreciate it.