JuanFernandez's blog

By JuanFernandez, history, 9 months 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

9 months ago, # |
  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;

  for( i = 0; line[i] != '\0'; ++i)
    if( line[i] == '?' )
      printf( "%" F64 "d\n", res);
      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.