sidereal's blog

Number of distinct substrings for each suffix (prefix) using suffix automaton.
By sidereal, history, 7 years ago, In English

I wonder if there's an easy way to solve this problem using suffix automaton. There's a linear solution for this problem using suffix tree (link to a much harder version of a problem).

  • Vote: I like it
  • +8
  • Vote: I do not like it

»
7 years ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

Yes, and very easily. For example, let's consider the following problem: How Many Substrings?. The solution is very concise:

void solution( void )
{
  int i, len = 0;

  res = 0;
  saInit();

  for( i = 0; line[i] != '\0'; ++i)
    if( line[i] == '?' )
      printf( "%" F64 "d\n", res);
    else
    {
      saExtend( line[i], ++len);
      res += len - last->link->len;
    }
}

and it's without any modification of SAu algorithm. Here last is the last SAu state (created while adding line[i] into SAu), res is the number of unique substrings of string's prefix, link is the suffix link.

→ Reply