[关闭]
@xzyxzy 2018-07-02T10:14:35.000000Z 字数 768 阅读 453

KMP

字符串

作业部落

评论地址


Border

表示(最长公共前后缀)
所以如果字符串的一个,那么可以看做是由一直循环得到的,循环节长度为
思想应用:「PKUSC2018」神仙的游戏」

Code

这篇博客够详细了 SYC
放一个模板怕忘
next3行,匹配三行,记得很多OJnext是关键字

  1. //洛谷3375
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<cstdlib>
  5. #include<cstring>
  6. #define next haha//有些时候next是关键字
  7. using namespace std;
  8. string s1,s2;
  9. int next[1000001];
  10. int main()
  11. {
  12. cin>>s1>>s2;
  13. int len1=s1.length();
  14. int len2=s2.length();
  15. //Part 1 next数组
  16. next[0]=-1;
  17. for(int i=1;i<=len2-1;i++)
  18. {
  19. int j=next[i-1];
  20. while(s2[j+1]!=s2[i]&&j!=-1)j=next[j];
  21. next[i]=s2[j+1]==s2[i]?j+1:-1;
  22. }
  23. //Part 2 匹配
  24. for(int i=0,j=0;i<len1;i++)
  25. {
  26. while(j&&s1[i]!=s2[j])j=next[j-1]+1;
  27. j+=s1[i]==s2[j]?1:0;
  28. if(j==len2){printf("%d\n",i-len2+2);j=next[j-1]+1;}
  29. }
  30. //Part 3 题目要求输出next
  31. for(int i=0;i<=len2-1;i++)
  32. printf("%d ",next[i]+1);
  33. printf("\n");
  34. return 0;
  35. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注