G_Hani's blog

Help in Suffix Array Problem
By G_Hani, history, 11 years ago, In English

Problem

you have a string S and two integers p and q and made a rule that names of the babies should be a substring of S, and the length should be between p and q (inclusive).

Now you are given S, p and q you have to find the number of distinct names that can be made.

Input :

The length of S will be between 2 and 10000 (inclusive) and S contains lowercase English letters only. The next line contains two integer p and q (1 ≤ p ≤ q ≤ length(S)).

output :

For each case, print the case number and the number of distinct names that can be made.

Sample :

input:

1

abcdef

2 5

answer:

Case 1: 14

I'm new with Suffix array, i already solve DISUBSTR. and here is my code.

i'm asking how i can modified my code to get the above problem AC ?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
11 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The idea is pretty much the same as for DISUBSTR with the only exception that you should count only distinct substrings with length between p and q.

Problem: http://lightoj.com/volume_showproblem.php?problem=1314
My solution: https://ideone.com/ljvMUW :)

PS: Note that on line 137 it's min(l,q) — letter L but it looks like min(1,q) — digit 1 :)

→ Reply