HDUOJ------Daydream字符查找-并求其始末位置

2013-07-17  10:50:38

Daydream

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 1423    Accepted Submission(s): 404

Problem Description

Welcome to 2009 HDU Girl’s Cup, bless you will happy in it. Every girl are beautiful if you use you heart to feel. Every corner in the world will colourful and energetic by several girls standing. If you boy, a normal bay, I believe that you will try to watch when a beautiful girl passing you and you will nervous if a girl watching you just when you are watching her.

Now give you a surprise that may be never happy in the real time. Millions of PLMM stand in a line and facing you(^_^). They are dress colourful clothings. You should to find out a maximal subline PLMM that their clothing color are all different.

Input

The input contains multiple test cases. Each case first give a integer n expressing many many girls stand in line.(n<=10000000) Next line a string including n character, each character standing one girls’s clothing color.

Output

Output one integer the numbers of maximal subline PLMM that their clothing color are all different and the line's begin and end (based from 0). If their are more answer, print the begin smallest.

Sample Input

3

abc

5

aaaba

8

hdugirls

Sample Output

3 0 2

2 2 3

8 0 7

初看这道题目，想到的是通过字符来定位，数组位置。但是却遇到一个问题，怎样来确定初始位置勒！！！，哎，纠结了大约一个小时，想到了一个方法，就是先确定字符不同的位置，然后就将每一次变化后的位置，设定为初始位置，当中还要比较不同字符的个数，如果变化了，那就要重新确定结束位置，依次这样，就可以了！！

当然由于后面i与i++的不确定，所以后面又加了一个判断语句来确保数据的无误！！！

Author

yifenfei

#include<iostream>
#include<string>
#include<vector>
namespace num
{
 int start,end,len,temp;
}
using namespace std;
int main( void )
{
  int n,i;
  string str;
  while(cin>>n)
  {
	  using namespace num;
	  vector<int>pos(128,-1);
      start=0,end=0,len=0,temp=0;
	  cin>>str;
	  for(i=0;i<n;i++)
	  {
          if(pos[str[i]]>=temp)
		  {
			  if(i-temp>len)
			  {
                len=i-temp;
                start=temp;
				end=i-1;
			  }
			  temp=pos[str[i]]+1;
		  }
		  pos[str[i]]=i;
	  }
	  
	  if(n-temp>len)
	  {
        len=n-temp;
		start=temp;
		end=n-1;
	  }
	 cout<<len<<" "<<start<<" "<<end<<endl;
  }
 return 0;
}