Генерация всех уникальных подстрок для данной строки

Question

С учетом строки s, какой самый быстрый метод для генерации набора всех его уникальных подстрок?

Пример: для str = "aba" мы бы получили substrs={"a", "b", "ab", "ba", "aba"}.

Наивным алгоритмом было бы обходить всю строку, генерируя подстроки длиной 1..n в каждой итерации, получая O(n^2) верхнюю границу.

Возможна ли лучшая граница?

(технически это домашнее задание, поэтому приветствуются только указатели)

Answer 1

Наивный алгоритм занимает время O (n ^ 3) вместо времени O (n ^ 2). Есть O (n ^ 2) количество подстрок. И если вы положите O (n ^ 2) количество подстрок, например, установить, затем set сравнивает O (lgn) сравнений для каждой строки, чтобы проверить, существует ли она в наборе или нет. Кроме того, для сравнения строк требуется время O (n). Поэтому, если вы используете set, это займет O (n ^ 3 lgn) времени. и вы можете уменьшить его O (n ^ 3) раз, если вы используете хеш-таблицу вместо set.

Дело в том, что это сравнение строк, а не сравнение чисел.

Таким образом, один из лучших алгоритмов, скажем, если вы используете суффиксный массив и алгоритм с самым длинным общим префиксом (LCP), он сокращает время O (n ^ 2) для этой задачи. Построение массива суффиксов с использованием алгоритма времени O (n). Время для LCP = O (n) время. Поскольку для каждой пары строк в массиве суффиксов, используйте LCP, чтобы общее время составило O (n ^ 2) времени, чтобы найти длину различных подстрок.

Кроме того, если вы хотите напечатать все отдельные подстроки, это займет O (n ^ 2) времени.

Answer 2

Вот мой код на Python. Он генерирует все возможные подстроки любой данной строки.

def find_substring(str_in):
    substrs = []
    if len(str_in) <= 1:
        return [str_in]

    s1 = find_substring(str_in[:1])
    s2 = find_substring(str_in[1:])

    substrs.append(s1)
    substrs.append(s2)
    for s11 in s1:
        substrs.append(s11)            
        for s21 in s2:            
            substrs.append("%s%s" %(s11, s21))

    for s21 in s2:
        substrs.append(s21)

    return set(substrs)

Если вы передадите str_ = "abcdef" в функцию, она выдаст следующие результаты:

a, ab, abc, abcd, abcde, abcdef, abcdf, abce, abcef, abcf, abd, abde, abdef, abdf, abe, abef, abf, ac, acd, acde, acdef, acdf, ace, acef , акф, объявление, аде, адеф, адф, ае, эйф, аф, б, бк, бкд, бкдэ, бкдеф, бкдф, бцэ, бчеф, бцф, бд, бдэ, бдэф, бдф, бе, беф, бф, с , cd, cde, cdef, cdf, ce, cef, cf, d, de, def, df, e, ef, f

Answer 3

Ваши программы не дают уникальных sbstrins.

Пожалуйста, проверьте с вводом abab и вывод должен быть aba,ba,bab,abab.

Answer 4

Это можно сделать только за время o (n ^ 2), поскольку общее количество уникальных подстрок строки будет равно n (n + 1) /2.

Пример:

string s = "abcd"

pass 0: (все строки имеют длину 1)

a, b, c, d = 4 строки

pass 1: (все строки имеют длину 2)

ab, bc, cd = 3 строки

проход 2: (все строки имеют длину 3)

abc, bcd = 2 строки

проход 3: (все строки имеют длину 4)

abcd = 1 строка

Используя эту аналогию, мы можем написать решение с o (n ^ 2) временной сложностью и постоянной пространственной сложностью.

Исходный код приведен ниже:

#include<stdio.h>

void print(char arr[], int start, int end)
{
    int i;
    for(i=start;i<=end;i++)
    {
        printf("%c",arr[i]);
    }
    printf("\n");
}


void substrings(char arr[], int n)
{
    int pass,j,start,end;
    int no_of_strings = n-1;

    for(pass=0;pass<n;pass++)
    {
        start = 0;
        end = start+pass;
        for(j=no_of_strings;j>=0;j--)
        {
            print(arr,start, end);
            start++;
            end = start+pass;
        }
        no_of_strings--;
    }

}

int main()
{   
    char str[] = "abcd";
    substrings(str,4);
    return 0;
}