程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Timus 1723. Sandro&#39;s Book 題解

Timus 1723. Sandro&#39;s Book 題解

編輯：C++入門知識

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 most 50.

Output

Output any of the most powerful spells, according to Sandro's definition.

Sample

input output

tebidohtebidoh

tebidoh

本題就看故事，故事看起來一長串，理解起來也挺費力，所以一開始我使用KMP算法查找了所有子串：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

class SandroBook
{
	vector 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<

上面程序可以AC。很sophisticated 的KMP算法。
但是後來一想，這個不對啊，子串包括了一個字母的子串，那麼本題就太簡單了，看起來甚至像是一個玩笑了。
經驗證的確如此，因為下面程序也能通過。教訓還是題意的問題，如果可以問，一定要先問清楚題意。大概本題出題者就是在開玩笑。
#include 
#include 

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;
}