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

aspe的博客

OI之路阻且长

 
 
 

日志

 
 

hdu3746  

2016-08-12 16:33:06|  分类: 解题报告 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
本文转载自liangpeiqi0《hdu3746》

【题目大意】

给你一个字符串,要求将字符串的全部字符最少循环2次需要添加的字符数。

(题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=3746

=====================================

【解题思路】

求最小覆盖子串公式,做一次kmp后,循环节的长度为len-next[len]。证明如图:

hdu3746 - 杨鸿飞 - 杨鸿飞的博客

 ====================================

AC代码】

#include <iostream>
#include <string>
#include <cstdio>

using namespace std;

const int ML=100000;

char st[ML+10];

int Next[ML+10];

int main()
{
//freopen("hdu3746.in","r",stdin);
//freopen("hdu3746.out","w",stdout);

ios::sync_with_stdio(false);

int t; cin>>t;

for ( ; t>0; t--)
{
scanf("%s",st+1);

int len=strlen(st+1);

Next[0]=Next[1]=0;

int k=0;

for (int i=2; i<=len; i++)
{
for ( ; st[k+1]!=st[i] && k>0; k=Next[k]);

if (st[k+1]==st[i]) k++;

Next[i]=k;
}

int p=len-Next[len]; //求出最小覆盖子串

//cout<<p<<endl;

if (len%p==0 && p!=len) cout<<0;
else cout<<p-len%p;

cout<<endl;
}

return 0;
}



 

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

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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