Where Am I?//枚举//排位1

2023-10-28 03:58

文章标签 枚举排位

本文主要是介绍Where Am I?//枚举//排位1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Where Am I?//枚举

题目

Farmer John has gone out for a walk down the road and thinks he may now be lost! Along the road there are N farms (1≤N≤100) in a row. Farms unfortunately do not have house numbers, making it hard for Farmer John to figure out his location along the road. However, each farm does have a colorful mailbox along the side of the road, so Farmer John hopes that if he looks at the colors of the mailboxes nearest to him, he can uniquely determine where he is.

Each mailbox color is specified by a letter in the range A…Z, so the sequence of N mailboxes down the road can be represented by a string of length N containing letters in the range A…Z. Some mailboxes may have the same colors as other mailboxes. Farmer John wants to know what is the smallest value of K such that if he looks at any sequence of K consecutive mailboxes, he can uniquely determine the location of that sequence along the road.

For example, suppose the sequence of mailboxes along the road is ‘ABCDABC’. Farmer John cannot set K=3, since if he sees ‘ABC’, there are two possible locations along the road where this consecutive set of colors might be. The smallest value of K that works is K=4, since if he looks at any consecutive set of 4 mailboxes, this sequence of colors uniquely determines his position along the road.

Input
The first line of input contains N, and the second line contains a string of N characters, each in the range A…Z.

Output
Print a line containing a single integer, specifying the smallest value of K that solves Farmer John’s problem.

Example
inputCopy
7
ABCDABC
outputCopy
4
题意
给你一串英文大写字母字符串，求一个最短长度，使该串中的相应长度子串无重复

思路

暴力枚举，注意代码书写避免tle

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <deque>
#include <queue>
#include <cmath>
#include <stack>
#define pi 3.1415926
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;int n;
char s[1000];
char temp[1000];
bool check(int start,int num){memset(temp,0,sizeof(temp));int cnt=0,num1=0,judge=0;;for(int i=start;i<start+num;i++)temp[cnt++]=s[i];for(int i=0;i+num<=n;i++){for(int j=0;j<cnt;j++){if(s[i+j]==temp[j]) judge=1;else judge=0;if(judge==0) break;}if(judge==1) num1++;judge=0;}if(num1>1) return false;else return true;
}
int main()
{scanf("%d",&n);scanf("%s",s);int judge=0;for(int i=1;i<=n;i++){             //枚举位数for(int j=0;j+i<=n;j++){       //从第一个邮箱开始枚举if(check(j,i)) judge=1;else judge=0;if(judge==0) break;}if(judge){printf("%d\n",i);break;}}return 0;
}