top of page

CCC 2003 S4 - Substrings


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)




Recent Posts

See All

CCC '24 J5 - Harvest Waterloo

#include<iostream> #include <vector> #include <algorithm> #include <cmath> #include <stack> using namespace std; int main() { int r, c, sr, sc; cin >> r; cin >> c; int p[r][c]; bool v

CCC '24 J4 - Troublesome Keys

#include <iostream> #include <string> #include <map> #include <vector> #include <algorithm> #include <cmath> using namespace std; int main() { string ps; string ds; cin >> ps; cin >> ds;

CCC '22 J5 - Square Pool

#include<iostream> #include <vector> #include <algorithm> #include <cmath> using namespace std; bool rowcom(pair<int, int> a, pair<int, int> b){ return a.first < b.first; } bool colcom(pair<int,

Comments


bottom of page