天书破解算法:消除重复子串,求最短长度
天书破解算法:消除重复子串,求最短长度
问题描述:
天书是由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 著作权归作者所有。请勿转载和采集!