[关闭]
@zzzc18 2017-11-09T11:39:50.000000Z 字数 656 阅读 1011

KMP

模板库 字符串


地址

数组究竟是什么?
即对于当前位置 ,模式串在 的部分完全相同
匹配的复杂度为 (这里不带证明)

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int MAXN = 1000000+9;
  6. char T[MAXN],P[MAXN];
  7. int next[MAXN];
  8. void GetFail(char *S){
  9. int len=strlen(S);
  10. for(int i=1;i<len;i++){
  11. int loc=next[i];
  12. while(loc && S[loc]!=S[i]){
  13. loc=next[loc];
  14. }
  15. next[i+1]=(S[loc]==S[i])?loc+1:0;
  16. }
  17. }
  18. void solve(){
  19. GetFail(P);
  20. int len=strlen(T);
  21. int goal=strlen(P);
  22. int loc=0;
  23. for(int i=0;i<len;i++){
  24. while(loc && T[i]!=P[loc])
  25. loc=next[loc];
  26. if(T[i]==P[loc])
  27. loc++;
  28. if(loc==goal)
  29. printf("%d\n",i+1-goal+1);
  30. }
  31. for(int i=1;i<=goal;i++)
  32. printf("%d ",next[i]);
  33. }
  34. int main(){
  35. scanf("%s%s",T,P);
  36. solve();
  37. return 0;
  38. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注