Блог пользователя sidereal

Number of distinct substrings for each suffix (prefix) using suffix automaton.
Автор sidereal, история, 5 лет назад, По-английски

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).

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить