正文
kuangbin专题十六 KMP&&扩展KMP HDU3746 Cyclic Nacklace
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
CC always becomes very depressed at the end of this month, he has checked his credit card yesterday, without any surprise, there are only 99.9 yuan left. he is too distressed and thinking about how to tide over the last days. Being inspired by the entrepreneurial spirit of "HDU CakeMan", he wants to sell some little things to make money. Of course, this is not an easy task.
As Christmas is around the corner, Boys are busy in choosing
christmas presents to send to their girlfriends. It is believed that
chain bracelet is a good choice. However, Things are not always so
simple, as is known to everyone, girl's fond of the colorful decoration
to make bracelet appears vivid and lively, meanwhile they want to
display their mature side as college students. after CC understands the
girls demands, he intends to sell the chain bracelet called
CharmBracelet. The CharmBracelet is made up with colorful pearls to show
girls' lively, and the most important thing is that it must be
connected by a cyclic chain which means the color of pearls are cyclic
connected from the left to right. And the cyclic count must be more than
one. If you connect the leftmost pearl and the rightmost pearl of such
chain, you can make a CharmBracelet. Just like the pictrue below, this
CharmBracelet's cycle is 9 and its cyclic count is 2:
Now CC has brought in some ordinary bracelet chains, he wants to
buy minimum number of pearls to make CharmBracelets so that he can save
more money. but when remaking the bracelet, he can only add color pearls
to the left end and right end of the chain, that is to say, adding to
the middle is forbidden.
CC is satisfied with his ideas and ask you for help.
InputThe first line of the input is a single integer T ( 0 < T <= 100 ) which means the number of test cases.
Each test case contains only one line describe the original ordinary
chain to be remade. Each character in the string stands for one pearl
and there are 26 kinds of pearls being described by 'a' ~'z' characters.
The length of the string Len: ( 3 <= Len <= 100000 ).OutputFor each case, you are required to output the minimum count of pearls added to make a CharmBracelet.Sample Input
Each test case contains only one line describe the original ordinary
chain to be remade. Each character in the string stands for one pearl
and there are 26 kinds of pearls being described by 'a' ~'z' characters.
The length of the string Len: ( 3 <= Len <= 100000 ).OutputFor each case, you are required to output the minimum count of pearls added to make a CharmBracelet.Sample Input
3
aaa
abca
abcde
Sample Output
0
2
5kmp求循环节。
推荐博客：https://www.cnblogs.com/chenxiwenruo/p/3546457.html
注意题目要求至少循环两次。所以判断条件需要写出来
#include<stdio.h>
#include<string.h>
int n,Next[],T,plen;
char p[]; void prekmp() {
plen=strlen(p);
int i,j;
j=Next[]=-;
i=;
while(i<plen) {
while(j!=-&&p[i]!=p[j]) j=Next[j];
if(p[++i]==p[++j]) Next[i]=Next[j];
else Next[i]=j;
}
} int main() {
//freopen("out","r",stdin);
scanf("%d",&T);
while(T--) {
scanf("%s",p);
prekmp();
//printf("%d**\n",Next[plen]);
int l=plen-Next[plen];
if(plen%l==&&plen/l>) printf("0\n");
else printf("%d\n",l-plen%l);
}
}
kuangbin专题十六 KMP&&扩展KMP HDU3746 Cyclic Nacklace的更多相关文章- kuangbin专题十六 KMP&;&;扩展KMP HDU2609 How many (最小字符串表示法)
Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me How man ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU2328 Corporate Identity
Beside other services, ACM helps companies to clearly state their “corporate identity”, which includ ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU1238 Substrings
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU3336 Count the string
It is well known that AekdyCoin is good at string problems as well as number theory problems. When g ...
- kuangbin专题十六 KMP&;&;扩展KMP POJ3080 Blue Jeans
The Genographic Project is a research partnership between IBM and The National Geographic Society th ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU2087 剪花布条
一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案.对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢? Input输入中含有一些数据,分别是成对出现的花布条和小 ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU1686 Oulipo
The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU1711 Number Sequence
Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M ...
- kuangbin专题十六 KMP&;&;扩展KMP HDU3613 Best Reward(前缀和+manacher or ekmp)
After an uphill battle, General Li won a great victory. Now the head of state decide to reward him w ...
随机推荐- 【转】使用SQL Tuning Advisor STA优化SQL
SQL优化器(SQL Tuning Advisor STA)是Oracle10g中推出的帮助DBA优化工具,它的特点是简单.智能,DBA值需要调用函数就可以给出一个性能很差的语句的优化结果.下面介绍一 ...
- Guava学习笔记：Guava新增集合类型-Multimap
在日常的开发工作中,我们有的时候需要构造像Map<K, List<V>>或者Map<K, Set<V>>这样比较复杂的集合类型的数据结构,以便做相应的业 ...
- 2016年江西理工大学C语言程序设计竞赛（高级组）
问题 A: jxust 解法:争议的问题(是输入整行还是输入字符串),这里倾向输入字符串,然后判断是否含有jxust就行 #include<bits/stdc++.h> using nam ...
- 文件流StreamReader和StreamWriter的使用
using (StreamReader sr = new StreamReader(@"C:\Users\shuai\Desktop\文件流读取.txt", Encoding.De ...
- Linux Shell编程(4): 逻辑运算符、逻辑表达式详解
shell的逻辑运算符 涉及有以下几种类型,因此只要适当选择,可以解决我们很多复杂的判断,达到事半功倍效果. 一.逻辑运算符 逻辑卷标 表示意思 1. 关于档案与目录的侦测逻辑卷标! -f 常用!侦测 ...
- wuzhicms 后台登录存留时间实现方式
在五指后台管理登录后,超过半小时不操作后台(不刷新页面或切换页面),就就会强制退出后台. 实现的思路是,在每次刷新页面都把当前时间存储下来,利用php的session机制来检测比对当前时间和数据库中存 ...
- Android API 中文（77）——AdapterView.OnItemSelectedListener
前言 本章内容是android.widget.AdapterView.OnItemSelectedListener,版本为Android 2.3 r1,翻译来自"cnmahj",欢 ...
- 前端控件之Jquery datetimepicker的使用总结
效果图 在介绍jquery datetimepicker的使用方法前,我们先来看一下它的实现效果图,这样以便让你更快地了解它是否是你所需要的. 下面我截了四张常用的效果图(截取自http://xdso ...
- linux 安装配置Jenkins
1.首先准备java环境,安装JDK 2.下载jenkins至Linux服务器 下载地址:https://wiki.jenkins-ci.org/display/JENKINS/Installing+ ...
- 认清Android框架 MVC，MVP和MVVM
编者按:现在很多时候,我们都是面向搜索(或 Google 或百度).GitHub 编程,那么,在早期没有互联网的情况下,该如何学习编程,成为一名真正的开发者?亦或是作为一名小白,如何进入互联网编程时代 ...
Give you n ( n < 10000) necklaces ,the length of necklace will not large than 100,tell me How man ...
Beside other services, ACM helps companies to clearly state their “corporate identity”, which includ ...
You are given a number of case-sensitive strings of alphabetic characters, find the largest string X ...
It is well known that AekdyCoin is good at string problems as well as number theory problems. When g ...
The Genographic Project is a research partnership between IBM and The National Geographic Society th ...
一块花布条,里面有些图案,另有一块直接可用的小饰条,里面也有一些图案.对于给定的花布条和小饰条,计算一下能从花布条中尽可能剪出几块小饰条来呢? Input输入中含有一些数据,分别是成对出现的花布条和小 ...
The French author Georges Perec (1936–1982) once wrote a book, La disparition, without the letter 'e ...
Given two sequences of numbers : a[1], a[2], ...... , a[N], and b[1], b[2], ...... , b[M] (1 <= M ...
After an uphill battle, General Li won a great victory. Now the head of state decide to reward him w ...
- 【转】使用SQL Tuning Advisor STA优化SQL
SQL优化器(SQL Tuning Advisor STA)是Oracle10g中推出的帮助DBA优化工具,它的特点是简单.智能,DBA值需要调用函数就可以给出一个性能很差的语句的优化结果.下面介绍一 ...
- Guava学习笔记：Guava新增集合类型-Multimap
在日常的开发工作中,我们有的时候需要构造像Map<K, List<V>>或者Map<K, Set<V>>这样比较复杂的集合类型的数据结构,以便做相应的业 ...
- 2016年江西理工大学C语言程序设计竞赛（高级组）
问题 A: jxust 解法:争议的问题(是输入整行还是输入字符串),这里倾向输入字符串,然后判断是否含有jxust就行 #include<bits/stdc++.h> using nam ...
- 文件流StreamReader和StreamWriter的使用
using (StreamReader sr = new StreamReader(@"C:\Users\shuai\Desktop\文件流读取.txt", Encoding.De ...
- Linux Shell编程(4): 逻辑运算符、逻辑表达式详解
shell的逻辑运算符 涉及有以下几种类型,因此只要适当选择,可以解决我们很多复杂的判断,达到事半功倍效果. 一.逻辑运算符 逻辑卷标 表示意思 1. 关于档案与目录的侦测逻辑卷标! -f 常用!侦测 ...
- wuzhicms 后台登录存留时间实现方式
在五指后台管理登录后,超过半小时不操作后台(不刷新页面或切换页面),就就会强制退出后台. 实现的思路是,在每次刷新页面都把当前时间存储下来,利用php的session机制来检测比对当前时间和数据库中存 ...
- Android API 中文（77）——AdapterView.OnItemSelectedListener
前言 本章内容是android.widget.AdapterView.OnItemSelectedListener,版本为Android 2.3 r1,翻译来自"cnmahj",欢 ...
- 前端控件之Jquery datetimepicker的使用总结
效果图 在介绍jquery datetimepicker的使用方法前,我们先来看一下它的实现效果图,这样以便让你更快地了解它是否是你所需要的. 下面我截了四张常用的效果图(截取自http://xdso ...
- linux 安装配置Jenkins
1.首先准备java环境,安装JDK 2.下载jenkins至Linux服务器 下载地址:https://wiki.jenkins-ci.org/display/JENKINS/Installing+ ...
- 认清Android框架 MVC，MVP和MVVM
编者按:现在很多时候,我们都是面向搜索(或 Google 或百度).GitHub 编程,那么,在早期没有互联网的情况下,该如何学习编程,成为一名真正的开发者?亦或是作为一名小白,如何进入互联网编程时代 ...
