hdu_2668 Daydream O(n)求最长不重复子串

showproblem.php?pid=2668

Daydream

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

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

Author

yifenfei

题意：　　O(n)求最长不重复子串，注意，这里的字符没有说是从a~z所以要取所有的ASCII（0~127 　因为是7位表示的）设置一个数组mp[127]表示对应字符出现在当前时期的前一个位置是哪里l ,r 表示扫描的左右端点，如果输入的ch 对应的mp[ch]>l 就要修改l的值为mp[ch]+1，这种O(n)的思想要注意的是输入输出容易超时，每次都申请读入是很耗费时间的，所以，开一个10000000的数组，直接用gets(s); 读入即可，下面是我超时的代码和ac的代码，可以看到真的有卡scanf的题、

 1 #include<cstring>
 2 #include <cstdio>
 3 #include<iostream>
 4 #include<algorithm>
 5 using namespace std;
 6 const int N = 1000;
 7 char s[10000006];
 8 int mp[N];
 9 int main()
10 {
11     int n,l,r,curL, len; //l, r 是最终答案
12     while(~scanf("%d",&n))
13     {
14         getchar();
15         gets(s);
16         len = 0;
17         curL = 0;
18         memset(mp,-1,sizeof(mp));
19         for(int i = 0; i < n; i++)
20         {
21             if(mp[s[i]] >= curL)
22             {
23                 if(i-curL > len)
24                 {
25                     len = i-curL;
26                     l = curL, r = i-1;
27                 }
28                 curL = mp[s[i]]+1;
29             }
30             mp[s[i]] = i;
31         }
32         if(n-curL > len) {
33             len = n-curL;
34             l = curL, r = n-1;
35         }
36         printf("%d %d %d
", len, l, r);
37     }
38     return 0;
39 }

下面是超时代码：

 1 #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int N = 26;
 5 int vis[N];
 6 
 7 int main()
 8 {
 9     int n;
10     while(~scanf("%d",&n))
11     {
12         memset(vis,-1,sizeof(vis));
13         char ch;
14         getchar();
15         int l=0, r=-1;
16         int len = 0;
17         int ansl = 0;
18         int ansr = -1;
19         int anslen = 0;
20         for(int i = 0; i < n; i++)
21         {
22             scanf("%c",&ch);
23             int tm = ch-'a';
24            //printf("tm = %d
",tm);
25             r++;
26             len++;
27             if(vis[tm]==-1){
28                 //vis[ch] = i;
29                 if(len>anslen){
30                     ansl = l;
31                     ansr = r;
32                     anslen = len;
33                 }
34             }
35             while(vis[tm]!=-1){
36                 for(int j = 0; j < 26; j++)
37                 {
38                     if(vis[j]==l) {
39                         vis[j] = -1;
40                         l++;
41                         len--;
42                         break;
43                         }
44                 }
45                 if(len>anslen){
46                     ansl = l;
47                     ansr = r;
48                     anslen = len;
49                 }
50             }
51             vis[tm] = i;
52         }
53         printf("%d %d %d
",anslen,ansl,ansr);
54     }
55     return 0;
56 }

View Code