-
Notifications
You must be signed in to change notification settings - Fork 1
/
Find Strings.py
110 lines (93 loc) · 2.52 KB
/
Find Strings.py
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#!/bin/python3
import math
import os
import random
import re
import sys
#
# Complete the 'palindromicBorder' function below.
#
# The function is expected to return an INTEGER.
# The function accepts STRING s as parameter.
#
def is_palin(s):
head, tail = 0, len(s) - 1
while head < tail:
if s[head] != s[tail]:
return False
head += 1
tail -= 1
return True
#key is a palin, value is the times it appears
def calc_palin_borders(palin_dict):
#print('palin_dict= ', palin_dict)
output = 0
for palin, times in palin_dict.items():
output += times * (times - 1) // 2
return output
def mono_str(s):
cc = s[0]
for c in s:
if c != cc:
return False
return True
def mono_str_result(s):
output = 0
for i in range(2, len(s) + 1):
output += i * (i - 1) // 2
output %= 1000000007
return output
def palindromicBorder(s):
if mono_str(s):
return mono_str_result(s)
output = 0
#palin tuple for substring of length 1
odd = [[], {}, 1]
for c in s:
if c not in odd[1]:
odd[1][c] = 0
odd[1][c] += 1
for i in range(len(s)):
odd[0].append(i)
output += calc_palin_borders(odd[1])
#print('odd = ', odd)
#palin tuple for substring of length 2
even = [[], {}, 1]
for i in range(len(s) - 1):
if s[i] == s[i + 1]:
even[0].append(i)
ss = s[i:i + 2]
if ss not in even[1]:
even[1][ss] = 0
even[1][ss] += 1
output += calc_palin_borders(even[1])
#print('even = ', even)
for l in range(3, len(s)):
#print('l = ', l)
#working tuple
if l % 2 == 0:
wt = even
else:
wt = odd
new_tuple = [[], {}, l]
for idx in wt[0]:
if idx - 1 >= 0 and idx + l - 2 < len(s) and s[idx - 1] == s[idx + l - 2]:
new_tuple[0].append(idx - 1)
ss = s[idx - 1:idx - 1 + l]
if ss not in new_tuple[1]:
new_tuple[1][ss] = 0
new_tuple[1][ss] += 1
#print('new_tuple= ', new_tuple)
output += calc_palin_borders(new_tuple[1])
output %= 1000000007
if l % 2 == 0:
even = new_tuple
else:
odd = new_tuple
return output
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
s = input()
result = palindromicBorder(s)
fptr.write(str(result) + '\n')
fptr.close()