G_Hani's blog

Help in Suffix Array Problem
By G_Hani, history, 8 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

»
8 years ago, # |
  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
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    P_Nyagolov i'm trying to solve the same problem ...

    i followed your step .. but then all answer got 0

    here is my code

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In line 123 if (n - s[i] < A) continue;

      It should be if (n - sa[i] < A) continue;, I think .

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what a silly mistake !!!

        finally AC :'(

        Thanks [user:Nooor][user:-Secta-]

        → Reply