Форум

рони · #21 (**permalink**) 17.02.2017, 16:33

Alexandroppolus,

abcdeahopwuns

Alexandroppolus · #22 (**permalink**) 17.02.2017, 16:39

рони,
действительно.

поправил )

white_raven · #23 (**permalink**) 17.02.2017, 18:04

Alexandroppolus, не сочтите за наглость, но Вы не могли бы немного описать словами своё решение? Хотя бы кратко - хотелось бы понять, а не просто восхититься)) Особенно вот тут интересно:

Сообщение от Alexandroppolus

if (pos >= start) {
            if (maxLength < i - start) {
                maxStart = start;
                maxLength = i - start;
            }
            start = pos + 1;
}

Буду очень признательна!

Alexandroppolus · #24 (**permalink**) 17.02.2017, 18:48

white_raven,

все просто и стандартно - ищем максимальный отрезок, для этого помним текущий наилучший результат, а в процессе обхода строки набираем отрезок-претендент.

Текущий максимум - в переменных maxStart и maxLength (начало и длина).

Претендент начинается с позиции start, его длина на каждой итерации равна (i - start).

В массиве map хранится последняя найденная позиция для каждой буквы. Процитированный тобой кусок - это когда на очередной итерации встретилась такая буква, которая уже есть в набираемом отрезке. Тогда прекращаем его набирать, смотрим, превзошел ли он максимум, если да, то сохраняем. И начинаем набирать новый отрезок со след. символа после найденной буквы.

Затраты по операциям - O(N), здесь меньше нельзя.

Paguo-86PK · #25 (**permalink**) 17.02.2017, 20:51

<style>
#start,#finish {
	color	: grey;
}
</style>
<script>
String.prototype.random = function(n) {
	var	c = "", s = "", z = 999;
	var	re = new RegExp(this);
	while(-- z && (!c.match(re) || (n -- && (s += c))))
		c = String.fromCharCode(Math.random() * 96 % 95 + 32);
	return	s;
}
String.prototype.module = function() {
	var	a = [],
		i = 0, j = 0,
		c,
		l = this.length,
		m = -1, k = -1;
	while(i < l) {
		for(j = 0; j < 128; a[j ++] = true);
		a[this.charCodeAt(j = i)] = false;
		while(a[this.charCodeAt(j + 1)])
			a[this.charCodeAt(++ j)] = false;
		if(m < j - i)
			k = i,
			m = j - i;
		++ i;
	}
	return	this.substr(k, m + 1);
}
//
function Print() {
	var	str = document.getElementById("cond").value.random(document.getElementById("wide").value);
	var	s = str.module();
	var	i = str.indexOf(s);
	document.getElementById("start").textContent = str.substring(0, i);
	document.getElementById("key").textContent = s;
	document.getElementById("finish").textContent = str.substring(i + s.length);
}
</script>
<body>
Ваш критерий
<input id=cond type=text value='[0-9_A-Z-a-z]' placeholder='Регулярное выражение' onChange='Print()' />
для
<input id=wide type=number min=1 max=96 value=48 onChange='Print()' /><a href='#' onmousemove='Print()'>Генерировать</a><br />
<span id=start></span><u id=key></u><span id=finish></span>
</body>