注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Minary_Acdream

http://f10.moe/

 
 
 

日志

 
 

[NBUT] 1180 Appreciate the Landscape  

2012-07-11 18:52:57|  分类: NBUT 2012 Summer |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

  • 问题描述
  • Ah, the landscape is so beautiful!
    The mountains are arranged one by one.
    Wait! I think the scenery is so familiar! The heights of mountains are the same as the mountains at the beginning!

    Give you the heights of N mountains (1 <= heights <= 95) and give you a number K. You should tell me how many times the heights of mountains will be same as the most front K Mountains.
  • 输入
  • This problem contains several cases.
    The first line of each case is two integers N and K (1 <= K <= N <= 50000).
    Then follow a line with N heights.
  • 输出
  • For each case, you should output how many times the heights of mountains will be same as the most front K Mountains.
  • 样例输入
  • 10 3 1 2 1 2 1 2 1 2 1 90 
  • 样例输出
  • 3 
    题目的要求是求和前N项相同的子序串。理解这个再将数字转换成字符串,就可以用 KMP 算法来做了。
    下面是我的代码:

    #include<iostream>
    #include<string.h>
    using namespace std;

    char A[50001],B[50001];
    int P[50001];
    const char hash[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz~!@#$%^&*()_+;’,./<>?\":{}|\\][=-` ";

    int kmp(int n, int k)
    {

    int i = 0, j = 0, cnt = 0;
    while(i < n)
    {
    if(j == -1 || A[i] == B[j])
    {
    i++;
    j++;
    }
    else j = P[j]; //不匹配时,j = p[j] 继续

    if(j == k) //完全匹配时 计数+1,j = p[j]继续
    {
    ++cnt;
    j = P[j];
    }
    }
    return cnt;

    }



    int main()
    {
    int N,K;
    while(~scanf("%d%d",&N,&K))
    {
    //数字转化成字符串
    for(int i = 0;i < N;i ++)
    {
    int num;
    scanf("%d",&num);
    A[i] = hash[num - 1];
    if(i < K) B[i] = hash[num - 1];
    }
    A[N] = B[K] = '\0';
    //P[]是为了让程序继续做下去,因为我们有可能找到多处匹配
    //预处理P数组
    memset(P, -1, sizeof(P));
    int i = 0,j = -1;
    while(i < K)
    {
    if(j == -1 || A[i] == A[j])
    {
    i++;
    j++;
    P[i] = j;
    }
    else j = P[j];
    }
    // for(i = 0;i < K;i ++)cout<<P[i]<<endl;
    printf("%d\n", kmp(N, K) - 1);
    }

    }




  评论这张
 
阅读(94)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018