专栏首页mlHDUOJ------Daydream字符查找-并求其始末位置

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • HDUOJ----Ignatius and the Princess III

    Ignatius and the Princess III Time Limit: 2000/1000 MS (Java/Others)    Memory L...

    Gxjun
  • HDUOJ----More is better(并查集)

    More is better Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 327680/10...

    Gxjun
  • HDUOJ---Piggy-Bank

    Piggy-Bank Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K...

    Gxjun
  • 聊聊应急响应

         应急响应分为四个阶段:前期沟通,事件处理,事件分析,报告交付,前期沟通主要是和客户交流事件情况,了解是什么安全事件,客户是否做了处理,如果做了处...

    crhua
  • HDUOJ----Ignatius and the Princess III

    Ignatius and the Princess III Time Limit: 2000/1000 MS (Java/Others)    Memory L...

    Gxjun
  • Android必知必会--事件分发机制

    所谓的安卓事件是什么?具体来说的就是点击和滑动两个操作;抽象着来说就是下面的表格。

    ClericYi
  • 勇士与公主(组合+完全背包)- HDU 1028

    这是一道排列组合题,然而却用到了完全背包的思想,寻找真相并不是件容易的事情,先简单看下题目,慢慢进入正题

    ACM算法日常
  • QingStor 对象存储发布新版本 Python SDK

    QingStor 对象存储近日发布了新版本的 Python SDK ,并开源在https://github.com/yunify/qingstor-sdk-py...

    BestSDK
  • 深入seajs源码系列一

    简述         前端开发模块化已经是大势所趋,目前模块化的规范有很多,众所周知的有commonJS,Module/Wrappings和AMD等,而且ES6...

    欲休
  • python的calcsize的妙用

      python的struct包让二进制文件的处理变的非常简单,通过unpack可以方便的进行把文件的内容读读取到变量里。

    py3study

扫码关注云+社区

领取腾讯云代金券