Перебор подмножеств. bash'а хватит?

Задача: перебрать все комбинации подстрок введенных строк. Строк может быть довольно много.

Кол-во комбинаций растет не медленнее экспоненты от кол-ва строк. Ты от программы запрашиваешь информации больше, чем компьютер сможет переварить. Что за задача?

Разве экспонента?
Количество комбинаций равно П(Ni-Ki+1) при i от 1 до M, где i - номер строки, M - количество строк, Ni - длина i-ой строки, Ki - длина подстроки для i-ой строки.

Итого для вышеприведенного мной примера количество комбинаций равно (6-2+1)*(8-5+1)=20

Для примера из 10 строк длиной 7 символов, с длиной подстроки 3 символа количество комбинаций равно (7-3+1)^10 = 9 765 625
В принципе, терпимо, на мой взгляд, если в выкладках нигде не ошибся.

А, ну да, с каждой новой строкой экспоненциальный рост, правильно.

>Что за задача?

Задача - сделать нечто вроде анаграммайзера, только составляющего слова не из перестановок букв, а из «нарезок» других слов.

>Для примера из 10 строк длиной 7 символов, с длиной подстроки 3 символа количество комбинаций равно (7-3+1)^10 = 9 765 625

Мне кажется баш повесится.

Perl же!

Python я знаю лучше. Хотя можно и на перле написать, алгоритм-то несложный.

Набросал по-быстрому на сях. Перебирает не подстроки заданной длинны, а вообще все возможны подстроки:

#include <stdio.h>
#include <string.h>

char* source[] = {"linux", "LOR", "trololo", "qwerty", "qwerty", "qwerty"};

#define NR (sizeof(source) / sizeof(source[0]))

struct {
	int begin;
	int end;
	int size;
} counters[NR];

int main(void) {

	int i;
	
	for (i = 0; i < NR; i++) {
		counters[i].size = strlen(source[i]);
		counters[i].begin = 0;
		counters[i].end = 1;
	}

	while (1) {

		for (i = 0; i < NR; i++) {
			fwrite(source[i] + counters[i].begin, 1, counters[i].end - counters[i].begin, stdout);
		}
		fputs("\n", stdout);

		i = 0;
		while (1) {
			counters[i].end++;
			if (counters[i].end > counters[i].size)
				counters[i].begin++,
				counters[i].end = counters[i].begin + 1;
			else
				break;

			if (counters[i].begin >= counters[i].size)
				counters[i].begin = 0,
				counters[i].end = 1,
				i++;
			else
				break;

			if (i >= NR)
				return 0;
		}

	}

	return 0;
}

Время выполнения для перебора 6-ти строк:

vadim@host3:~/tmp$ gcc -O2 bla.c && time ./a.out > /dev/null

real	0m10.627s
user	0m9.306s
sys	0m0.090s

> Мне кажется баш повеселится.

fix :)

> int main(void)

зачем void в аргументах?

зачем void в аргументах?

В Сях хорошим тоном считается указывать void в списке параметров, т.к. компилятор не подставляет его автоматически, если список пуст, в отличие от Си++. Пустой список параметров означает «функция с неспецифированным списком параметров».

vadim@host3:~/tmp$ cat > 1234.c
void f1() {}
void f2(void) {}
void f3() { 
f1(1);   
f2(1);
}
vadim@host3:~/tmp$ gcc -c 1234.c
1234.c: В функции ‘f3’:
1234.c:5:1: ошибка: слишком много аргументов в вызове функции ‘f2’
1234.c:2:6: замечание: declared here
Status: 1
vadim@host3:~/tmp$

А в main просто поставил по привычке.

Понятно, спасибо.

если длина первого слова - m, длина второго слова - n, то обрезков первых слов не больше m(m-1), а второго - n(n-1), => вариантов, которые можно составить конкатенацией обрезков, получается не более m(m-1)n(n-1). С условием ограничения на длину результата еще меньше.