[关闭]
@lychee123 2017-08-18T23:11:29.000000Z 字数 818 阅读 873

POJ 3461:Oulipo(KMP求小串在大串中的最多匹配次数)

数据结构


题面链接

  1. #include<stdio.h>
  2. #include<string.h>
  3. #include<algorithm>
  4. using namespace std;
  5. const int maxn=1e6+6;
  6. int Next[maxn];
  7. void getnext(char s[])//对小串的处理
  8. {
  9. int l=strlen(s);
  10. Next[0]=-1;
  11. int j=-1;
  12. for(int i=1;i<l;i++)
  13. {
  14. while(j>=0&&s[j+1]!=s[i])
  15. j=Next[j];
  16. if(s[j+1]==s[i])
  17. j++;
  18. Next[i]=j;
  19. }
  20. }
  21. int getfind(char s[],char s1[])//大串s与小串s1的匹配
  22. {
  23. int l=strlen(s);
  24. int l1=strlen(s1);
  25. int i,j=-1,ans=0;
  26. for(i=0;i<l;i++)
  27. {
  28. while(j>=0&&s1[j+1]!=s[i])
  29. j=Next[j];
  30. if(s1[j+1]==s[i])
  31. j++;
  32. if(j==l1-1)
  33. ans++;
  34. }
  35. return ans;
  36. }
  37. char s1[10010];
  38. char s[1000010];
  39. int main()
  40. {
  41. int n;
  42. scanf("%d",&n);
  43. while(n--)
  44. {
  45. memset(Next,0,sizeof(Next));
  46. scanf("%s",s1);
  47. scanf("%s",s);
  48. getnext(s1);
  49. int ans=getfind(s,s1);
  50. printf("%d\n",ans);
  51. }
  52. return 0;
  53. }

利用容斥原理计数. 设长度为 , 恰好用了 个字符的方案数为 , 那么


添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注