天书破解算法:消除重复子串,求最短长度

问题描述:

天书是由26个大写英文字母组成的长字符串。天书的破解依赖于以下消除操作:每次消去长度大于2的极长相同字母子串。'极长'的意思该子串的两端不能是这子串的字母。例如,'JKWWWWLB'的包含'W'的极长相同子串是中间'WWWW',而'WW'不是极长子串。消去'WWWW'子串后,结果子串为'JKLB'。

通过多次消除操作,能得到长度最短的结果子串就是破解的天书。请你设计一种方案,输出天书破解后的字符数。

输入格式:

数据有若干行。每一行只有一个字符串S。当S为'0'时,表示输入结束。

输出格式:

按照输入的顺序,输出天书破解后的字符数,每个数字占一行。

输入示例:

JKWWWWLB
AAABBBA
WWKKAAAKWA
0

输出示例:

4
0
1

C++ 代码:

#include <iostream>
#include <string>

using namespace std;

int main() {
    string s;
    while (cin >> s && s != "0") {
        int len = s.length();
        int count = 0;
        for (int i = 0; i < len; i++) {
            int j = i + 1;
            while (j < len && s[j] == s[i]) {
                j++;
            }
            if (j - i > 2) {
                i = j - 1;
            } else {
                count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}
天书破解算法:消除重复子串,求最短长度

原文地址: https://www.cveoy.top/t/topic/ozWs 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录