HDU 2668 Daydream 最长不重复子序列 尺取法

缘起

日常浪费生命~ HDU 2668 Daydream

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
给定的序列中最长的连续的没有重复字符的子序列的长度，以及起始位置，如果有多处，输出最前面的一组

【输入】
多样例. 见样例, 字符串的长度达到了 1e7

【输出】
对每个样例,输出长度、起止索引

【样例输入】
3
abc
5
aaaba
8
hdugirls

【样例输出】
3 0 2
2 2 3
8 0 7

【限制】
1s

其实就是【1】而已。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//#include "stdafx.h"
#include <stdio.h>
#include <string.h>
//#define LOCAL

const int maxn = 1e7+5;
char s[maxn];
int n;

int v[256];

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d", &n))
	{
		int ans = 0, start = -1;
		scanf("%s", s);
		memset(v,0, sizeof(v));
		for (int i = 0,j=0; i<n;i++)
		{
			if (++v[s[i]]==1)
			{
				if (ans<i-j+1) // 如果真的优于之前的
				{
					ans = i-j+1;
					start = j;
				}
			}
			else
			{
				while(s[j]!=s[i])
				{
					--v[s[j++]];
				}
				v[s[j++]] = 1;
			}
		}
		printf("%d %d %d\n", ans, start, start+ans-1);
	}
	return 0;
}

ac情况

Status Accepted
Time 218ms
Memory 10988kB
Length 647
Lang G++
Submitted 2019-10-11 15:23:25
Shared
RemoteRunId 30862071

【1】https://yfsyfs.github.io/2019/10/11/lintcode-384-%E6%9C%80%E9%95%BF%E6%97%A0%E9%87%8D%E5%A4%8D%E5%AD%97%E7%AC%A6%E7%9A%84%E5%AD%90%E4%B8%B2-%E5%B0%BA%E5%8F%96%E6%B3%95/