This is a string handling question.
When you solve it, you can use two for loop to generate all substring, then place all to one set, the result is the set size. but the solution is not a linear solution, it is n*n, n is the string length. TLE will be coming. but you can get 8 points.
Linear solution:
if input string is S, build a list suffix that contains all sub string, linear to do it and sort the suffix. Then handling suffix list.
count = len(suffix[0]) + 1
if j > 0 and j < len(S)
count = len(suffix[j]) - LCP(suffix[j - 1], suffix[j])
LCP(suffix[j - 1], suffix[j]) is a function to get these two prefix common chars number. You can use the naive method to code the function:
def LCP(s1, s2):
for i in range(min(len(s1), len(s2))):
if s1[i] != s2[i]:
return i
return min(len(s1), len(s2))
Naive solution:
T = int(input())
result = []
table = set()
for i in range(T):
ss = input()
m = 1
for i in range(1,len(ss)+1):
for j in range(0,len(ss)+1-i):
s = ss[j:i+j]
table.add(s)
m += len(table)
table.clear()
result.append(m)
for x in result:
print(x)
Sufifx solution:
def LCP(s1, s2):
for i in range(min(len(s1), len(s2))):
if s1[i] != s2[i]:
return i
return min(len(s1), len(s2))
N = int(input())
for i in range(N):
S = input()
suffix = []
for j in range(len(S)):
suffix.append(S[j:])
suffix.sort()
count = len(suffix[0]) + 1
for j in range(1, len(S)):
count += len(suffix[j]) - LCP(suffix[j - 1], suffix[j])
print(count)
Comments