17.02.2017, 16:33
|
|
Профессор
|
|
Регистрация: 27.05.2010
Сообщений: 33,124
|
|
Alexandroppolus,
abcdeahopwuns
|
|
17.02.2017, 16:39
|
|
Профессор
|
|
Регистрация: 25.10.2016
Сообщений: 1,012
|
|
рони,
действительно.
поправил )
|
|
17.02.2017, 18:04
|
Интересующийся
|
|
Регистрация: 23.11.2016
Сообщений: 19
|
|
Alexandroppolus, не сочтите за наглость, но Вы не могли бы немного описать словами своё решение? Хотя бы кратко - хотелось бы понять, а не просто восхититься)) Особенно вот тут интересно:
Сообщение от Alexandroppolus
|
if (pos >= start) {
if (maxLength < i - start) {
maxStart = start;
maxLength = i - start;
}
start = pos + 1;
}
|
Буду очень признательна!
|
|
17.02.2017, 18:48
|
|
Профессор
|
|
Регистрация: 25.10.2016
Сообщений: 1,012
|
|
white_raven,
все просто и стандартно - ищем максимальный отрезок, для этого помним текущий наилучший результат, а в процессе обхода строки набираем отрезок-претендент.
Текущий максимум - в переменных maxStart и maxLength (начало и длина).
Претендент начинается с позиции start, его длина на каждой итерации равна (i - start).
В массиве map хранится последняя найденная позиция для каждой буквы. Процитированный тобой кусок - это когда на очередной итерации встретилась такая буква, которая уже есть в набираемом отрезке. Тогда прекращаем его набирать, смотрим, превзошел ли он максимум, если да, то сохраняем. И начинаем набирать новый отрезок со след. символа после найденной буквы.
Затраты по операциям - O(N), здесь меньше нельзя.
|
|
17.02.2017, 20:51
|
|
Профессор
|
|
Регистрация: 16.09.2009
Сообщений: 253
|
|
<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>
Последний раз редактировалось Paguo-86PK, 17.02.2017 в 23:53.
Причина: Улучшил прототип генератора и добавил стиль
|
|
17.02.2017, 23:11
|
Интересующийся
|
|
Регистрация: 23.11.2016
Сообщений: 19
|
|
Alexandroppolus, спасибо большое! Просто огромное
И всем всем, спасибо!!
|
|
17.02.2017, 23:17
|
Интересующийся
|
|
Регистрация: 23.11.2016
Сообщений: 19
|
|
Paguo-86PK, ничего себе! Расширенный вариант до прототипов ещё не дошла, но спасибо!
|
|
17.02.2017, 23:56
|
|
Профессор
|
|
Регистрация: 16.09.2009
Сообщений: 253
|
|
|
|
08.03.2017, 13:43
|
|
junior
|
|
Регистрация: 29.11.2011
Сообщений: 3,924
|
|
Сообщение от Poznakomlus
|
alert(Array.from(new Set("abcdeahopwunshslge")).join(''));
|
вернет алфавит, а не подстроку
__________________
Чебурашка стал символом олимпийских игр. А чего достиг ты?
Тишина - самый громкий звук
|
|
09.03.2017, 12:40
|
|
Профессор
|
|
Регистрация: 13.03.2013
Сообщений: 1,572
|
|
nerv_,
совершенно верно
Когда мы прочтем, что такое подстрока, то поймем, что максимальная подстрока от слова является словом
|
|
|
|