[hdu]求最长不重复子串

佚名 6年前 (2019-05-11) 随笔 1693人围观抢沙发百度已收录

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2668

Daydream

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

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

abc

5 aaaba 8 hdugirls

Sample Output

3 0 2 2 2 3 8 0 7

正确解法：

开一个mp[s[i]]=i 数组，记录每个元素最后的位置。

如果这个元素出现了，并且在（开始字串）之后。（说明重复了）

说明这个字串已经是当前所能得到的最大不重复字串了，更新最大值。

开始字串为这个元素的后一位。

最后n要特判。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 #include <set>
 7 #include <map>
 8 #include <vector>
 9 #include <cctype>
10 #include <sstream>
11 using namespace std;
12 typedef long long ll;
13 const int inf=0x7fffffff;
14 const int N=100000+100;
15 const int M=50000+10;
16 const int MOD=10007;
17 const double PI=acos(-1.0);
18 char s[10000006];
19 int n;
20 int mp[300];
21 int main()
22 {
23     while(scanf("%d",&n)!=EOF)
24     {
25         getchar();
26         gets(s);
27         memset(mp,-1,sizeof(mp));
28         int len=0,l=0,r=0,cur=0;
29         for(int i=0;i<n;i++)
30         {
31             if(mp[s[i]]>=cur)
32             {
33                 if(i-cur>len)
34                 {
35                     len=i-cur;
36                     l=cur;  r=i-1;
37                 }
38                 cur=mp[s[i]]+1;
39             }
40             mp[s[i]]=i;
41         }
42         if(n-cur>len)
43         {
44             len=n-cur;
45             l=cur;  r=n-1;
46         }
47         printf("%d %d %d\n",len,l,r);
48     }
49 
50 
51     return 0;
52 }