QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#502564#3259. Substring CharactersyundaehyuckAC ✓57ms10880kbPython31.2kb2024-08-03 09:43:292024-08-03 09:43:36

Judging History

你现在查看的是最新测评结果

  • [2024-08-03 09:43:36]
  • 评测
  • 测评结果:AC
  • 用时:57ms
  • 内存:10880kb
  • [2024-08-03 09:43:29]
  • 提交

answer

def generalized_period(s):
    return set(s)

def minimal_proper_substrings(s, gen_period):
    n = len(s)
    minimal_substrings = set()
    
    for i in range(n):
        for j in range(i + 1, n + 1):
            if j - i < n:  # ensure proper substring
                substr = s[i:j]
                if set(substr) == gen_period:
                    minimal_substrings.add(substr)
    
    # filter out non-minimal substrings
    minimal_proper_substrings = set()
    for substr in minimal_substrings:
        is_minimal = True
        for k in range(1, len(substr)):
            if set(substr[:k]) == gen_period or set(substr[k:]) == gen_period:
                is_minimal = False
                break
        if is_minimal:
            minimal_proper_substrings.add(substr)
    
    return minimal_proper_substrings

def count_minimal_unique_proper_substrings(s):
    gen_period = generalized_period(s)
    minimal_substrings = minimal_proper_substrings(s, gen_period)
    return len(minimal_substrings)

import sys
input = sys.stdin.read
data = input().splitlines()

for line in data:
    if line.strip():
        result = count_minimal_unique_proper_substrings(line)
        print(result)

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 12ms
memory: 10412kb

input:

aabbabb
abAB34aB3ba7
104001144
aaabcaaa
a
bb
bd
1234567

output:

2
1
3
2
0
1
0
0

result:

ok 8 lines

Test #2:

score: 0
Accepted
time: 19ms
memory: 10808kb

input:

kejfASKDNF2342389fjsl2lsklsdflkjdKDFJKFD2342359829jdkjfkdklsjekfw234234234235123
11111111111111111111111111111111111111111111111111111111111111111111111111111111
12312343123123142312341234123412341234123423412312341234123232312341232341234123

output:

1
1
11

result:

ok 3 lines

Test #3:

score: 0
Accepted
time: 23ms
memory: 10760kb

input:

1234543212345432123454321234543212345432123454321234543212345432123454321
1234543212345432123454321234543212345432123454321234543212345432123454321Z
a1234543212345432123454321234543212345432123454321234543212345432123454321
ABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCDEFABCD...

output:

2
1
1
6
1
1
25
2
1
1
1
0
0
1
1
4
5
2
1
1
1
1

result:

ok 22 lines

Test #4:

score: 0
Accepted
time: 57ms
memory: 10880kb

input:

0123456789ABCDEFEDCBA9876543210123456789ABCDEFEDCBA98765432123456789ABCDEFEDCBA
abcdeadbedcacdebadecbdaecdbacebdcaebecadebacebdabecdcbeabedcebdadbcecbdaedbcacb
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZzyxwvutsrqponmlkjihgfedcbaqdKYJt2iHEL3vWFghr
99RBKQEBTBCA8WRSVNBSCGVZFLPTP7F29965694YAKW3B77CCFXCNEWRRL8...

output:

2
32
1
2
1
2
2
1
2
1
1
8
7
8
13
1
6
3
2
1
1
1

result:

ok 22 lines

Test #5:

score: 0
Accepted
time: 31ms
memory: 10672kb

input:

x
dddddddgggggg
dgdgdgdgdgdg
ef1ef1e
ef1ef1
abcbacbacab
cabcbacbacabc
kadksfkaddkdfakkjdfjdfasjdafhgdafsdasflalsdlkhdfhdasjklsadkjdafhklsajfghdasjkdg
1234567890
1234567890987654321
ssss
aba
ec26hb6a4l2wv3rm1ut7r9nxtejs5riidbxenodgipyjjuxtdwi3bykyhnauvv5gvws8r7fxdady7ek8
q3g12voqn3mewezr1jfoejpgh4vc4...

output:

0
1
2
3
3
5
5
6
0
2
1
2
1
1
1
1
1
1
1
7
4
1

result:

ok 22 lines