Timus 1723. Sandro's Book 题解

Input

Output

Sample

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

但是后来一想，这个不对啊，子串包括了一个字母的子串，那么本题就太简单了，看起来甚至像是一个玩笑了。

经验证的确如此，因为下面程序也能通过。教训还是题意的问题，如果可以问，一定要先问清楚题意。大概本题出题者就是在开玩笑。

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

Timus 1723. Sandro's Book 题解,布布扣,bubuko.com

Timus 1723. Sandro's Book 题解

原文：http://blog.csdn.net/kenden23/article/details/24491141