Уникальная подстрока
Добрый вечер, форумчане!
Новичок просит помощи в решении следующей задачи (не прошу за меня решить - просто хотя бы подсказать, в какую сторону смотреть): Необходимо реализовать функцию, которая принимает строку, состоящую из латинских букв. Функция должна вернуть максимальную УНИКАЛЬНУЮ подстроку. Пример: строка: abcdeahopwunshslge ответ: bcdeahopwuns Цикл, substring, indexOf.. - не собирается. Пожалуйста помогите. |
Именно в таком порядке - bcdeahopwuns? Может так?
var s = 'abcdeahopwunshslge', u;
u = s.split('').reduce(function(p, c, i, a) {
if(!~p.indexOf(c)) p.push(c);
return p
}, []).join('');
alert(u)
|
Спасибо, что откликнулись!
Именно в таком.. Я так поняла, что искомая подстрока подбирается с первого символа, до первого повторяющегося, а потом из этих вариантов выбирается максимально длинный, т.е.: 'abcdeahopwunshslge', а в ней: abcde bcdeahopwuns cdeahopwuns deahopwuns eahopwuns и т.д. |
:)
var str = "abcdeahopwunshslge";
myRe = /(\S)(?![\s\S]+?\1)/gm;
alert(str.match(myRe).join(""));
|
Цитата:
|
!!! У меня сейчас глаза сломаются :yes:
Спасибо большое!! Но вы не могли бы хотя бы в 2-х словах объяснить, что произошло? :)) |
Я и не знаю, такая задача (
|
Цитата:
Представьте себе, что у вас в ящике фрукты. Ваша задача взять из него только по одному каждого вида. Какие фрукты в нем вы не знаете, пока не откроете ящик. Можно ли перед его открытием задать условие брать фрукты из ящика в обязательной последовательности: яблоко, груша? Если этих фруктов в ящике не будет, то возникает коллизия - задача взять по одному фрукту выполнима, но в тоже время задача в целом не будет не выполнима так как нельзя будет разложить их в требуемом порядке. В вашем примере символы исходной строки также неизвестны, а значит задание порядка в выводе именно таким bcdeahopwuns создает коллизию. А если так задается, значит и решать никакой задачи не надо, ответ уже задан в порядке - bcdeahopwuns. С неизвестной входной строкой не создать коллизии можно только в том случае, если порядок в результате будет описан условиями или закономерностями. Применительно к вашему порядку, например - первый символ алфавита (а), если только он есть, должен следовать в порядке четвертым и т.п. А иначе никак (хотя это от лукавого, в контексте массивов и это можно сделать, но должно быть условие). Цитата:
|
Вы, конечно, правы, спасибо, что всё так подробно расписали. Я же потому и обратилась с вопросом, потому что непонятна задача.
Но я дословно представила здесь условия и пример. Цитата:
А что произошло - это я об этом: Цитата:
|
alert(Array.from(new Set("abcdeahopwunshslge")).join(''));
:) |
function maxUniqSubStr(str) {
if (!str) { return ''; }
var map = { };
var maxLength = 1;
var maxStart = 0;
var start = 0;
map[str[0]] = 0;
for (var i = 1, le = str.length; i < le; ++i) {
var c = str[i];
var pos = map[c];
if (pos != null && pos >= start) {
if (maxLength < i - start) {
maxStart = start;
maxLength = i - start;
}
start = pos + 1;
}
map[c] = i;
}
if (maxLength < i - start) {
maxStart = start;
maxLength = i - start;
}
return str.substr(maxStart, maxLength);
}
alert(maxUniqSubStr('abcdeahopwunshslge'));
|
рони, Poznakomlus,
у вас в ответе не подстрока ) |
Цитата:
Но опять такие нет ответа на то, в чем ищется. Пример от рони работает, ибо строка: abcdeahopwunshslge и ответ: bcdeahopwuns А теперь этим же решением, что получится если строка будет, например - abcdeaahopwunshslge. Уже не верно, так? А для входной строки dabcdeaahopwunshslge решение от Poznakomlus тоже даст не тот результат. Другими словами ответ в задаче уже сам по себе подогнан. ) |
Цитата:
|
Ребята!! Вы все такие умные :)
Уух, буду разбираться теперь Спасибо огромное за помощь!!:thanks: |
Подстрока в строке abcdeahopwunshslge
var str = 'abcdeahopwunshslge',
limit,
maxSS = '',
j,
indx,
arr = [];
for(var i = 0; i < str.length; i++) {
arr[i] = '';
j = i ;
limit = str.length;
while(j < limit) {
arr[i] += str[j];
indx = str.indexOf(str[j], j + 1);
if(indx >= 0 && limit > indx ) { limit = indx;}
j++;
}
}
for (var i = 0; i < arr.length; i++) {
if (maxSS.length < arr[i].length) { maxSS = arr[i];}
}
alert(maxSS);
|
Dilettante_Pro,
:victory: |
:write: :)
function fn(b) {
for (var c = "", f = /(\S)(?=\S+?\1)/, a = 0; a < b.length; a++)
for (var d = a + 1; d <= b.length; d++) {
var e = b.substring(a, d);
if (f.test(e)) break;
else e.length > c.length && (c = e)
}
return c
};
var str = 'abcdeahopwunshslge';
alert(fn(str));
|
рони,
Я так и знал, что появится такой вариант:victory: Я же просто реализовал алгоритм, описанный ТС в пост 3 |
Ускорил свой вариант в 10 раз :) используется массив вместо объекта для карты последних вхождений.
function maxUniqSubStr(str) {
if (!str) { return ''; }
var map = [];
for (var i = 0; i < 256; ++i) {
map[i] = -1;
}
var maxLength = 1;
var maxStart = 0;
var start = 0;
for (var i = 0, le = str.length; i < le; ++i) {
var c = str.charCodeAt(i);
var pos = map[c];
if (pos >= start) {
if (maxLength < i - start) {
maxStart = start;
maxLength = i - start;
}
start = pos + 1;
}
map[c] = i;
}
if (maxLength < i - start) {
maxStart = start;
maxLength = i - start;
}
return str.substr(maxStart, maxLength);
}
alert(maxUniqSubStr('abcdeahopwunshslge'));
|
Alexandroppolus,
abcdeahopwuns |
рони,
действительно. поправил ) |
Alexandroppolus, не сочтите за наглость, но Вы не могли бы немного описать словами своё решение? Хотя бы кратко - хотелось бы понять, а не просто восхититься)) Особенно вот тут интересно:
Цитата:
|
white_raven,
все просто и стандартно - ищем максимальный отрезок, для этого помним текущий наилучший результат, а в процессе обхода строки набираем отрезок-претендент. Текущий максимум - в переменных maxStart и maxLength (начало и длина). Претендент начинается с позиции start, его длина на каждой итерации равна (i - start). В массиве map хранится последняя найденная позиция для каждой буквы. Процитированный тобой кусок - это когда на очередной итерации встретилась такая буква, которая уже есть в набираемом отрезке. Тогда прекращаем его набирать, смотрим, превзошел ли он максимум, если да, то сохраняем. И начинаем набирать новый отрезок со след. символа после найденной буквы. Затраты по операциям - O(N), здесь меньше нельзя. |
<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>
|
Alexandroppolus, спасибо большое! Просто огромное :)
И всем всем, спасибо!! |
Paguo-86PK, ничего себе! Расширенный вариант :) до прототипов ещё не дошла, но спасибо!
|
Цитата:
P.S.: Чуточку доработал пример…:yes: |
Цитата:
|
nerv_,
совершенно верно Когда мы прочтем, что такое подстрока, то поймем, что максимальная подстрока от слова является словом :lol: |
| Часовой пояс GMT +3, время: 12:19. |