It's been quite a number of years since Lich Sandro retired. Sometimes in the evenings, when he feels especially lonely, he takes a book that was presented to him by his student magicians on the occasion
of his retirement.
This evening the great magician is also reading the book. One of the chapters describes Sandro's famous discovery: he invented a universal spell many years ago. Any substring (a few consecutive symbols
of the string) of the universal spell is also a spell, and its power is equal to the number of times this spell is encountered in the universal spell (for example, the string “ue” encounters in the string “queue” twice, and the string “aba” encounters in the
string “abababa” three times).
Sandro has a lot of free time now and he wants to find the most powerful spell. Help Sandro do it.
Input
The only input line contains the universal spell invented by Sandro. The spell is a non-empty string consisting of lowercase English letters with length at most50.
Output
Output any of the most powerful spells, according to Sandro's definition.
Sample
input
output
tebidohtebidoh
|
tebidoh
|
本题就看故事, 故事看起来一长串, 理解起来也挺费力,所以一开始我使用KMP算法查找了所有子串:
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <map>
using namespace std;
class SandroBook
{
vector<int> tbl;
int encounter;
string spell;
public:
SandroBook():tbl(), encounter(0)
{
}
int kmpSearch(string txt, string pat, int sta=0)
{
tbl.resize(pat.size());
genTbl(pat);
int c = 0;
for (int i = 0, j = 0; i < txt.size(); i++)
{
if (pat[j] == txt[i]) j++;
else if (j > 0)
{
j = tbl[j-1];
i--;
}
if (pat.size() == j)
{
c++;
j = tbl[j-1];
}
}
return c;
}
void genTbl(const string &pat)
{
for (int i = 1, j = 0; i < pat.size(); i++)
{
if (pat[i] == pat[j]) tbl[i] = ++j;
else if (j > 0)
{
j = tbl[j-1];
i--;
}
}
}
void SandroRun()
{
string txt;
cin>>txt;
encounter = 0;
for (int i = 0; i < txt.size(); i++)
{
for (int d = i+1; d < txt.size(); d++)
{
string pat = txt.substr(i, d-i+1);
int c = kmpSearch(txt, pat, i+1) + 1;
if (c > encounter)
{
encounter = c;
spell = pat;
}
}
}
cout<<spell;
}
};
上面程序可以AC。很sophisticated 的KMP算法。
但是后来一想,这个不对啊,子串包括了一个字母的子串,那么本题就太简单了,看起来甚至像是一个玩笑了。
经验证的确如此,因为下面程序也能通过。教训还是题意的问题,如果可以问,一定要先问清楚题意。大概本题出题者就是在开玩笑。
#include <iostream>
#include <stdio.h>
using namespace std;
int mainSandro()
{
char str[50];
int maxi,max,i=0;
int ch[26]={0};
scanf("%s",&str);
while(str[i++]) ch[str[i]-'a']++;
maxi=0;
max=ch[maxi];
for(i=1;i<26;i++)
{
if(ch[i]>max)
{
maxi=i;
max=ch[maxi];
}
}
printf("%c\n",maxi+'a');
return 0;
}
分享到:
相关推荐
Preface......................... Serdijn, Sandro A. P. Haddad, Jader A. De Lima ............ 369 Hermans ............................................................................................. 395
Sandro Tosi - Matplotlib for Python Developers (2009)
Mastering Node.js By Sandro Pasquali (Packt 2013).pdf Node.js for PHP Developers (OReilly 2013).pdf Node.js the Right Way (Pragmatic 2013).pdf Pro.Node.js.for.Developers (Apress 2013).pdf Professional...
移相器课程:通过移相器https://sandro.github.iophaser-lessons进行编程课程
桑德罗·佩雷拉(Sandro Pereira)的在线作品集 您好,我叫Sandro Pereira,这是我的在线投资组合。 我写这篇文章主要是为了我的利益,因为我倾向于忘记事情。 文档很重要! 我在用什么 ,因为变量和嵌套样式使事情...
主节点 “掌握 Node.js”一书中的练习 - Sandro Pasquali
This book is intended to be a first introduction to deep learning. Deep learning is a special kind of learning with deep artificial neural networks, although today deep learning and artificial neural ...
测试和重构遗留代码Sandro Mancuso 重构 kata 的 .NET 版本(见链接)。代码 git clone https://github.com/orient-man/TripServiceKata.gitcd TripServiceKatagit checkout demo-start使用 git 导航重构步骤有用的 ...
由Sandro Mancuso制作的重构遗留代码kata。 我涵盖了他的仓库中的指南,该指南包括对TripService类进行单元测试,并对其进行重构,以打破依赖关系,并以表达域的精心设计的代码结尾。 这是Sandro Mancuso的存储库...
Introduction to Deep Learning From Logical Calculus to Artificial Intelligence
Sandro可让您监视矿石人的事物,并提供他们的位置和状态。
桑德罗 公司计算机存储库 我的做法
....-- sandro26 GB超级稳定的性能及较快的速度和较小的资源占用正是现在其他IE内核浏览器所欠缺的,也是我们最需要的,因此GB是最好的IE内核浏览器。 ....-- wjse 同样很喜欢GB!!喜欢她的纤细、喜欢她的自由制定 ...
积分java源码(由Sandro Stucky设计的标志 - 取自 Martin Odersky 的演讲The Evolution of Scala ,2015)。 该库实现了以下数据类型: data.Dequeue data.Either data.Heap data.List data.NonEmpty data.Maybe ...
风险风险团队(Alen、Shane、Alex、?)
详细介绍了linux系统的各个版本及特性,linux爱好者值得拥有
DJ-VJ DJ / VJ,用于音频和视频技术文档文档任务:音频和视频技术创建DJ / VJ工具桑德罗·霍夫曼(sandro Hoffmann)s0555061托马斯·基尔(Thomas Kirsch)s0554325罗伯特·布朗斯特(Robert Bronst)s0555313...
git clone https://github.com/Sandro1977/automacao-test-checklist.git 克隆存储库后,打开Eclipse IDE并导入项目。 运行类br.com.automacao.paripassu.TesteNovoCadastroAvaliado.java作为JUnit测试。
> mythical-creatures@1.0.0 test /Users/Sandro/Code/Simplon/mythical-creatures > mocha " exercises/1/unicorn.test.js " Unicorn - should instantiate our good friend, Unicorn - should have a name - ...
它目前由 Sandro Mani 维护。 建造 要构建此模块,请确保安装了健全的开发包。 然后,键入: python setup.py build 为了安装模块类型: python setup.py install 对于一些基本文档,请查看文件 sanedoc.txt ...