Description
话说实验室有个胖子叫小明,还有个瘦的叫小兵,小兵他已经来了好几天啦,ls也一直叫他练打英文字母,小兵就没有小明听话,他老是偷懒,ls想让他动动脑筋,于是就给他出了个问题来惩罚他偷懒。现在我们把两个英文字母的ASCII码的差的绝对值称为这两个字符的“距离”,如果给你一个字符串和上面定义的“距离”的值,问小兵在这个串里最长的连续的子串有多长?当然这个子串的任意两个字符的距离一定不超过给定的距离值!亲爱的同学们,如果你们同情瘦个子小兵,那么你就帮他写个程序,计算一下符合要求的子串最长到底是多少?
Input
假定字符串都是由英文小写字母组成的,长度不超过100000。输入有两行,第一行是整数d即指给定的距离值,d>=0;另一行是字符串。
Output
输出也有两行,第一行的格式是:“From=XX,To=XX”,第二行的格式是:“MaxLen=XX”。本问题有多组测试数据。如果有多组符合要求的解,那么输出起始位置最小的解。
Sample Input
2
vdtjajcrnamkzequrcnojumsjnbyzsotkebnrkycbvbmcsqdvjght
15
hpenlvlknkrtpmkmkbxcpbbpxxipxmgxnysryttuowyxppgmndoxzizdilnjdqawieab
Sample Output
From=11,To=12
MaxLen=2
From=32,To=46
MaxLen=15
#include <iostream>
#include <string>
using namespace std;
int main()
{
int d;
string s;
while (cin >> d >> s)
{
int from = 0, to = 0, maxLen = 0;
for (size_t i = 0; i < s.length(); i++)
{
size_t j = i;
char min = s[i];
char max = s[i];
while (j < s.length() && (max - min) <= d)
{
j++;
if (s[j] < min)
min = s[j];
if (s[j] > max)
max = s[j];
}
if (int(j - i) > maxLen)
{
from = i + 1;
to = j;
maxLen = j - i;
}
}
cout << "From=" << from << ",To=" << to << '\n';
cout << "MaxLen=" << maxLen << '\n';
}
return 0;
}