从交易ID生成密钥的程序 [英] Program that generate key from transaction ID

问题描述

事务ID S是仅由小写字母字符组成的字符串，即[a，z]中的S [i].如果在长度为K的S的每个子串中的[a，z]中至少存在一个字符C，则称K为S的可能关键字. ID的密钥是此类可能的Ks的最小值.

输入:

第一行包含交易ID S(1< = length< = 1000000)

输出:

交易ID的密钥，即最小可能密钥Ks.

例如

输入:
zbcde
输出
3


输入:
bbbbb
输出
1

输入:
zbzczbz
输出
2

我尝试过的事情:

Transaction ID S is a string consisting of only lower-case alphabetic character i.e S[i] in [a,z] . K is said to be a possible key of S, if there exists at least one character C in [a,z] in each and every substring of S of length K . Key of ID is minimum of such possible Ks.

Input:

first line contains Transaction ID S (1<=length<=1000000)

Output:

Key of Transaction ID i.e Minimum of possible keys Ks.

e.g

Input:
zbcde
Output
3


Input:
bbbbb
Output
1

Input:
zbzczbz
Output
2

What I have tried:

#include<iostream>
#include<string>
using namespace std;

int main()
{
	string s;
        string s2[100000];
	int pos=2,flag=1,i,j;
	cin>>s;
	int n= s.size();
	for (i=0; i<n; i++)
	{
		if (s[i]==s[i+1])
		flag=0;
		pos=1;
	}
	while(flag){
	for (i=0; i<n-1; i++)
	{
		s2[i]=s.substr(i,pos);
		
		for (j=0; j<pos; j++)
		{
			if (s2[i][j]==s2[i+1][j])
			flag=1;
			
			else
			{
				flag=0;
				pos++;
			}
		}
		
	}
}

cout<<pos<<endl;

return 0;

}

推荐答案

我建​​议您首先查看同学的表现:

I suggest you start by looking at how your classmates are doing: How to solve this problem of strings and keys?[^]

这篇关于从交易ID生成密钥的程序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！