UVa 261 - The Window Property

#哈希 #set

Published on 2016-01-14

描述

给定一个长度为 $n(n\le100)$ 的字符串。如果对于任意 $k \in [1, n]$ ，该字符串所有长度为 $k$ 的子串中都有不超过 $k+1$ 个不同的字符串，那么这个字符串就是 window property。如果不是的话，找出所有 $k$ 中下标（这里的下标指的是子串结束的位置，从 $1$ 开始）最小的不符合的位置。

样例输入

ababcababa
0010100100
0010101001

样例输出

NO:5
YES
YES

附加输入

011110011010110000010110001111000111010111101001010100100011101010111010101001010000
1101000010000110001110100010011101011111111110110101100101110001010101011110001010000
101111100110110
0111110011010011100000
01110010101010011001000111001
01100001011100100000100
00100000110011110100111101110010000000001101010001100010110111110110110100000010100
000110100010000111001001110010010111101100100000100010000001011100010010001101111100100101100
100010000011110
10110111010110110111110011110
110100011001001111101011000010010000000000100101011110001000101101101100000010011111011101111
01011010
100111100111110011100001111101111110000
10001100000100011100011110
1100001110110111010101000101001011001110101000101111110110010110000111111011001101110101101100100100
1100010010001100101010010001000010011010000111111010111111001000001001011100001100111001011111001
0100011101110101110100011001011011011001110010100110100100000101100001100101
11011001011101111001000110010111110011100010100000101100101110101101011110100100000110110
0011011101010010011111110000101000111001000001010001
1101101111010111101111000110101011101000
0001110101011110011011001001001001110110111001100011010110000101000011001011
00101100111101110000101010111101
1100001110110110111100001110101101101111110101010100111100101111001010111101000001010100000111010111
001110111110010110111000000110100011011100101101010101101000010010
11111100100001011100000101110111000011001001110
00111101010011111011111010111101110000000001010110001001010100001101101111
101001100111101011010111100011100000110101110011000011001010000001010001010000100101000011011111010
10110010000010101100001110011000110111110111111001010101111011100110001011010110101110011
10001110101000101101011100101001101011001111000100
011110111110000011100011011011010011001110000000110101000000111010110
001001001101000101111000011001001
111100100100001110
110000011110001100000000010000001001111000000011001
0000100110101000110110110000000001111100001101110101110
1100110101011001010001100111011000011001000110011001111110010010010100001010111
1100111001101101000010001100010110100000010100111110000110101110010010010010001111111100110
10111010010011111010100000110101
0000110011100010110010001101010011000001111110011011
1100110010100101110000100000110000111111001010101
00010000011001110001101110100000000100101111000
0100101000110111010011110001010000010101110001101110001100001001010100
01000110001101011011110001111111111100110101000010101111000
11100111110000100101100111001100011100001001010000000010110000011100000100101101101000010010001
111111111010100001010000000000011111100000110110001000
101101110
0100
000110010110110000100011000
000110000110000100100000000100110101100111110
1000011111110111000011110010010110111001010010010
0101101001100010100010101001001011100000011010010110100010110
110000001000110100010000010000110110010100110100110010011111100101100010001010
01100111001111111001000110011000110101
01011100100011100101110101100110010100111000110100011000000011010010100000011001
110110110101001011111101110100011000000010110
011111110001001010000000011111111000111001100001001001101010101001001
011111110110111010
000010011
0001110
0111011101010010010001100111110101100010111111110010100101110100010011010
0110010111011000101101101011111000001010111
110011010111101110111110111000100101101
1011100001010101011110110111000101011000101111000010001010110011110100110010010011
01000000101010000110101100100010110010000100110000010110100111100000000111110110111100111010100
0101100111010110011011101000110100011000100011010110010
110000001010100000000010010001010000000101111000000011110110010010000010010110
101011101000110110010000010000101100011111100101
001010100111010110101110001000101100110101010001101011111011011101111001110011101110001101000100
111
1110110000111111101000010001111000101101101110001001001001110001011101111001011110110011100110
11111101001100101110111000111100111001111100110101100100111011001001100
1110
1110110010111101100101100011101010001001010100000010001000110010110011110
11111100001101111010000011101000111011011101110010010001010110101000011101111110
00000101111101110111
010111100000010011110110000111000111000010011011010001000011
01011111100000111010010000000100
0101011001100011101001011111110100001111001101011111100011100110111110010000101000110011
1100000011111011110100110010011101110111001000110010001011
10000111110110011010011110001100100001110000001110011101111001000000011010000011011011100011111
011001
01101111110101000011010111111011101011110100110110011010101
00011110011000011100100001011101100011100001010101011010111001111101011111000010111
10101001011101010101101101000110000101100001100100
10000100101101010100100011001
10010101111111010001111101001110111001101
101111010100001110001010000101111000101011000111111010110100011110110010110101010100011
001010110001011101100110110100100001110110011
110010111001111111101011010001011010111010
111000101001011010011100011011100001111011110000101011011010110010101011000010001100110011
00000010101000101111001110111010110110110110100001100011101010000111100110100
001111000111100000111010110010101010110001101101110110101100
10000011110010000101010000110101011011100111110100001001010010011111001100011010010101000011
1000111010010111011011001010101011101000001000101101001110
010100001011010011000101111001000010011110011101001011000100001110110011011001
01010110000001110011010100000111010001001111001000101001001000101110010101
00000001101101001100011000111001000100000110
100000101101010100100010010100010001011101010100111100101101100100001110011101110
0
01110101111111111011100010110001110001110001010111001100100100011111010010111000110101111
011100001011001100100111010101110000100001000110010000101110001011101101

附加输出

NO:7
NO:6
NO:9
NO:8
NO:6
NO:5
NO:10
NO:6
NO:11
NO:11
NO:6
YES
NO:5
NO:6
NO:7
NO:6
NO:7
NO:7
NO:5
NO:11
NO:7
NO:6
NO:7
NO:6
NO:9
NO:7
NO:7
NO:6
NO:6
NO:13
NO:10
NO:7
NO:8
NO:9
NO:5
NO:5
NO:8
NO:7
NO:5
NO:11
NO:10
NO:7
NO:6
NO:15
YES
YES
NO:6
NO:6
NO:7
NO:9
NO:9
NO:5
NO:7
NO:14
NO:10
NO:12
NO:9
NO:7
NO:11
NO:5
NO:5
NO:7
NO:11
NO:7
NO:9
NO:8
NO:11
YES
NO:8
NO:10
YES
NO:8
NO:11
NO:9
NO:8
NO:10
NO:9
NO:9
NO:7
NO:5
NO:11
NO:8
NO:11
NO:9
NO:9
NO:9
NO:8
NO:5
NO:7
NO:13
NO:7
NO:8
NO:6
NO:9
NO:9
NO:10
NO:9
YES
NO:7
NO:6

分析

由于 $n \le 100$ ，预处理出哈希，对于每一个 $k$ 扫一遍，同一长度的子串加入 set，判断 set.size() 就好了。
注意字符串中可能有空格！请用 gets 或者 cin.getline。看来任何没说有没有空格的题目都要小心。

代码

//  Created by Sengxian on 1/14/16.
//  Copyright (c) 2015年 Sengxian. All rights reserved.
//  UVa 261 哈希 + 模拟
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <set>
using namespace std;
typedef unsigned long long ull;
const int maxn = 100 + 5;
const ull hashBase = 100007;
char str[maxn]; ull powers[maxn], h[maxn]; int n;

void process() {
    h[n] = 0;
    for(int i = n - 1; i >= 0; --i) h[i] = h[i + 1] * hashBase + str[i];
}

inline ull getHash(int l, int r) {
    return h[l] - h[r] * powers[r - l];
}

int main() {
    powers[0] = 1;
    for(int i = 1; i < maxn; ++i) powers[i] = powers[i - 1] * hashBase;
    while(gets(str) != NULL) {
        int pos = maxn + 1;
        n = strlen(str);
        process();
        for(int k = 1; k <= n; ++k) {
            set<ull> s;
            for(int i = 0; i + k - 1 < n; ++i) {
                s.insert(getHash(i, i + k));
                if(s.size() > k + 1) {
                    pos = min(pos, i + k);
                    break;
                }
            }
        }
        if(pos == maxn + 1) puts("YES");
        else printf("NO:%d\n", pos);
    }
    return 0;
}

UVa 10795 - A Different Task UVa 1402 - Robotic Sort

Sengxian's Blog

UVa 261 - The Window Property

描述

样例输入

样例输出

附加输入

附加输出

分析

代码