设为首页收藏本站
开启辅助访问 切换到宽版

 找回密码
 立即注册

QQ登录

只需一步，快速开始

热门： 51单片机 | 24小时必答区 | 单片机教程 | 单片机DIY制作 | STM32 | Cortex M3 | 模数电子 | 电子DIY制作 | 音响/功放 | 拆机乐园 | Arduino | 嵌入式OS | 程序设计

搜索
»论坛 › 电子技术分类讨论区 › 程序设计/上位机 › HDU1711 C++源码
返回列表 发新帖
查看: 1404|回复: 0
打印 上一主题 下一主题
收起左侧

HDU1711 C++源码

[复制链接]
跳转到指定楼层
楼主
ID:409739 发表于 2018-10-15 09:47 | 只看该作者 |只看大图 回帖奖励 |倒序浏览 |阅读模式
HDU1711工程包：


C++源程序如下:
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <vector>
  4. #include <cstring>
  5. #define MAX 1000100
  6. #define M 10010
  7. using namespace std;
  8. int a[MAX];
  9. int b[M];
  10. int NEXT[M];

  12. class Number_Sequence
  13. {
  14.     int p,len1,len2;
  15. public:
  16.     void initial();
  17.     void read();
  18.     void computing();
  19.     void result();
  20.     void getnext();
  21.     void kmp();
  22. };

  24. void Number_Sequence::initial()
  25. {
  26.     memset(a,0,sizeof(a));
  27.     memset(b,0,sizeof(b));
  28.     memset(NEXT,0,sizeof(NEXT));
  29.     p=-1;
  30. }

  32. void Number_Sequence::read()
  33. {
  34.     scanf("%d%d",&len1,&len2);
  35.     for(int i=0;i<len1;i++)
  36.     {
  37.         scanf("%d",&a[i]);
  38.     }
  39.     for(int i=0;i<len2;i++)
  40.     {
  41.         scanf("%d",&b[i]);
  42.     }
  43. }

  45. void Number_Sequence::getnext()
  46. {
  47.     NEXT[0]=-1;
  48.     int j=0,k=-1;
  49.     while(j<len2)
  50.     {
  51.         if(k==-1||b[j]==b[k])
  52.         {
  53.             if(b[++j]==b[++k])
  54.             {
  55.                 NEXT[j]=NEXT[k];
  56.             }
  57.             else
  58.                 NEXT[j]=k;
  59.         }
  60.         else
  61.             k=NEXT[k];
  62.     }
  63. }

  65. void Number_Sequence::kmp()
  66. {
  67.     int i=0,j=0;
  68.     while(i<len1&&j<len2)
  69.     {
  70.         if(j==-1||a[i]==b[j])
  71.         {
  72.             i++;
  73.             j++;
  74.         }
  75.         else
  76.         {
  77.             j=NEXT[j];
  78.         }
  79.         if(j==len2)
  80.         {
  81.             p=i-j+1;
  82.             break;
  83.         }
  84.     }
  85.     if(j!=len2)
  86.     {
  87.         p=-1;
  88.     }
  89. }

  91. void Number_Sequence::computing()
  92. {
  93.     getnext();
  94.     kmp();
  95. }

  97. void Number_Sequence::result()
  98. {
  99.     cout<<p<<endl;
  100. }

  102. int main()
  103. {
  104.     Number_Sequence ns;
  105.     int cases;
  106.     scanf("%d",&cases);
  107.     for(int i=0;i<cases;i++)
  108.     {
  109.         ns.initial();
  110.         ns.read();
  111.         ns.computing();
  112.         ns.result();
  113.     }
  114.     return 0;
  115. }
复制代码

所有资料51hei提供下载:
HDU 1711.rar (241.11 KB, 下载次数: 5)


分享到:  QQ好友和群QQ好友和群 QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友
收藏收藏 分享淘帖 顶顶 踩踩
回复

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

手机版|小黑屋|51黑电子论坛 |51黑电子论坛6群 QQ 管理员QQ:125739409;技术交流QQ群281945664

Powered by 单片机教程网

快速回复 返回顶部 返回列表