URAL 1723. Sandro’s Book

Author: 2015-11-17

ACM

, , ,

1. 题目

http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=18392

1723. Sandro’s Book

Time limit: 0.5 second
Memory limit: 64 MB

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
Problem Author: Ivan Burmistrov (prepared by Olga Soboleva)
Problem Source: Ural Regional School Programming Contest 2009

2. 思路

巫妖Sandro对咒语的最新科研结果表明，一条咒语的子序列也是咒语，且该子序列咒语的强度与该子序列咒语在完整咒语中出现的次数成正比。给出一条咒语，求其中包含的最强咒语。

求字符串中重复次数最多的子序列。题目对子序列的长度并没有要求，单个字符也可以算作一个子序列，于是问题变成了求字符串中重复次数最多的字符。

3. 代码

#include <cstdio>
#include <cstring>

const int MAX_LENGTH = 51;

void solveP9a_SandrosBook();

int main() {
    solveP9a_SandrosBook();
    return 0;
}

void solveP9a_SandrosBook() {
    int cnt[26], max = 0;
    char str[MAX_LENGTH], maxChar;
    scanf("%s", str);

    memset(cnt, 0, 26 * sizeof(int));

    for (int i = 0; i < strlen(str); ++i) {
        ++cnt[str[i] - 'a'];
    }

    for (int i = 0; i < 26; ++i) {
        if (cnt[i] > max) {
            max = cnt[i];
            maxChar = i + 'a';
        }
    }

    printf("%c\n", maxChar);
}