С Новым годом! Форум программистов, компьютерный форум, киберфорум
JavaScript для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.60/40: Рейтинг темы: голосов - 40, средняя оценка - 4.60
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 11

В одномерном массиве найти количество повторяющихся последовательностей символов с длиной больше или равной двум

11.11.2018, 23:55. Показов 8767. Ответов 60
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Условие : В одномерном массиве символов найти количество повторяющихся последовательностей символов с длиной больше или равной двум. Например, в строке «abcdbabcba» ответ: «ab», «bc», «abc», «ba». Не использовать строковые функции.

Подскажите, пожалуйста, как можно это реализовать для последовательностей с длиной больше 2 символов, и как правильно подсчитать количество повторяющихся последовательностей?

Прикрепляю набросок кода:
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
let a = prompt("Введите символьный массив");
let result = [];
let count = 0;
for(let i = 0; i < a.length-1; i++)
{
    result.push(a[i] + a[i+1])
}
for(let i = 0; i < result.length; i++)
{
    for(let j = 0; j < result.length; j++)
    {
        if(result[i] == result[j])
            count ++;
    }
}
 
alert(count);
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
11.11.2018, 23:55
Ответы с готовыми решениями:

В одномерном массиве символов найти количество повторяющихся последовательностей символов
В одномерном массиве символов найти количество повторяющихся последовательностей символов с длиной больше или равной двум. Например, в...

В одномерном массиве символов найти количество повторяющихся последовательностей символов
Добрый вечер! Есть такая программа:В одномерном массиве символов найти количество повторяющихся последовательностей символов с длиной...

В одномерном массиве символов найти количество повторяющихся последовательностей символов
В одномерном массиве символов найти количество повторяющихся последовательностей символов с длиной больше или равной двум. Например, в...

60
 Аватар для diadiavova
7258 / 2605 / 744
Регистрация: 11.04.2015
Сообщений: 4,149
Записей в блоге: 43
12.11.2018, 00:24
loreleysatellit, в строке ababab следует ли считать, что подстрока abab встречается дважды?
0
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 11
12.11.2018, 00:28  [ТС]
Да, "abab" встречается дважды в "ababab"
0
 Аватар для diadiavova
7258 / 2605 / 744
Регистрация: 11.04.2015
Сообщений: 4,149
Записей в блоге: 43
12.11.2018, 06:35
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
        function qwerty(a)
        {
            let subs = [];
            let findIndecies = startIndex => a.map((v, i) => i).filter(v => v > startIndex && a[startIndex] == a[v] && a[startIndex + 1] == a[v + 1]);
            let getMax = (i1, i2) =>
            {
                let result = 2;
                while (a[i1 + result] == a[i2 + result]) result++;
                return result;
            }
            let addToSubs = s =>
            {
                let ind = subs.findIndex(v => s.indexOf(v) > -1);
                if (ind > -1) subs[ind] = s;
                else if (subs.findIndex(v => v.indexOf(s) > -1) > -1) { }
                else subs.push(s);
            }
            for (let start = 0; start < a.length - 2; start++)
                findIndecies(start).map((v) => a.slice(v, v + getMax(start, v)).join("")).forEach(addToSubs);
            let calc = n => n * (n - 1) / 2;
            return subs.reduce((s, v) => s + calc(v.length), 0);
        }
 
        console.log(qwerty("abcdbabcba".split("")));
loreleysatellit, В силу того, что получилось несколько сложновато, функцию надо бы протестировать, но на контрольном примере выдает 4, как и ожидалось.
Я там в одном месте все-таки со строками выполнял некоторые манипуляции, конкретно в функции addToSubs у строки вызывается indexOf. Это дело можно поправить, реализовав подобную функцию для массива, но это уже сам, если нужно.
1
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 11
12.11.2018, 08:12  [ТС]
Поняла, спасибо Вам большое
0
супермизантроп
Эксперт JS
3941 / 2979 / 692
Регистрация: 18.04.2012
Сообщений: 8,629
12.11.2018, 10:22
loreleysatellit, где-то около года назад по работе решал подобную задачку, но в более общем виде: определить все имеющиеся повторяющиеся подмассивы в явном виде плюс указать частоту вхождения для каждого подмассива

решал, используя "традиционный" яваскрипт (т.е. без "мулек" ecma-2015 типа map, filter, reduce)

надо для вас поискать файл с тем решением?
0
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 11
12.11.2018, 15:25  [ТС]
kalabuni, да, если Вам не сложно) Интересно посмотреть на разные алгоритмы решения этой задачи
0
566 / 465 / 183
Регистрация: 14.10.2017
Сообщений: 1,259
12.11.2018, 16:44
можно так, в императивном стиле
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
let strTxt = 'abcdbabcbabcd';
const getRepeat = str => {
    let res = {};
    const equal = (a, b, len) => {
        for(let k = 0; k < len; k++){
            if(str[a++] != str[b++])
                return false;
        }
        return true;
    }
    const incl = (obj, prop) => {
        for(let key in obj)
            if(key == prop)
                return true;
        return false;
    }
    const getProp = (p, len) => {
        let tmp = '';
        for(let m = 0, n = p; m < len; m++)
            tmp += str[n++];
        return tmp;
    }
    for(let x = 2; x < str.length - 1; x++){
        for(let i = 0, flag = false; i < str.length - x; i++, flag = false){
            if(incl(res, getProp(i, x)))
                continue;
            for(let j = i + 1; j < str.length; j++){
                if(equal(i, j, x)){
                    if(!flag){
                        res[getProp(i, x)] = 1;
                        flag = true;
                    }
                    else
                        res[getProp(i, x)]++;
                }
            }
        }
    }
    return res;
}
console.log(getRepeat(strTxt));
ab: 2
abc: 2
abcd: 1
ba: 1
bab: 1
babc: 1
bc: 2
bcd: 1
cd: 1
1
0 / 0 / 0
Регистрация: 23.09.2018
Сообщений: 11
12.11.2018, 18:39  [ТС]
Оо, интересно, спасибо)
0
Эксперт JS
6496 / 3907 / 2006
Регистрация: 14.06.2018
Сообщений: 6,781
12.11.2018, 19:17
PHP/HTML
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
<!DOCTYPE html>
<html>
<head>
    <meta charset="UTF-8">
</head>
<body>
    <script>
        let str = "abcdbabcba",
            // Превратить строку в массив символов, не используя строковые функции
            a = Array.from(str), 
 
            maxPos = a.length - 2,
            array = [], // Все подстроки от двух символов
            array2 = []; // Повторяющиеся подстроки от двух символов
        for (let i = 0; i <= maxPos; ++i) {
            for (let j = 2, maxLength = a.length - i; j <= maxLength; ++j)
                array.push(a.slice(i, i + j).join(""));
        }
        array.sort();
        let prev = "",
            count = 0;
        for (let i = 0; i < array.length; ++i) {
            if (array[i] === prev)
                ++count;
            else {
                if (prev && count > 1)
                    array2.push(prev);
                count = 1;
                prev = array[i];
            }
        }
        if (prev && count > 1)
            array2.push(prev);
 
        console.log(array2);
    </script>
</body>
</html>
1
12.11.2018, 20:28

Не по теме:

Цитата Сообщение от loreleysatellit Посмотреть сообщение
Не использовать строковые функции
Хм... И чего я удалил свой ответ?..

0
 Аватар для diadiavova
7258 / 2605 / 744
Регистрация: 11.04.2015
Сообщений: 4,149
Записей в блоге: 43
13.11.2018, 02:51
Цитата Сообщение от Lazy_Den Посмотреть сообщение
Хм... И чего я удалил свой ответ?..
Вообще, его можно было доработать, просто реализовав замену indexOf и удаление дубликатов, в остальном код можно было минимально изменить, так что действительно удалять было незачем. ))

loreleysatellit, В своем коде я нашел проблему, а именно на строку "ababab" выдает результат 6, в то время как должен быть 5. Так что код не канает. Отметку о лучшем ответе убрал сам))
В принципе с циклами тут уже были варианты, так что предложу вот это
JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
        function qwerty(array)
        {
            const exist = (start, rng) => !!(array.slice(start).find((v, i, ar) => rng.every((vv, ii) => vv == ar[i + ii])));
            const findRanges = (start) => array.slice(start).map((v, i, a) => a.slice(0, i + 1))
                .filter((v, i) => v.length > 1 && exist(start + 1, v))
            const eq = (a1, a2) => a1.length == a2.length && a1.every((v, i) => v == a2[i]);
            return array.map((v, i) => findRanges(i)).reduce((s, v) => s.concat(v), [])
                .filter((v, i, a) => a.findIndex((vv, ii) => eq(v, a[ii])) == i)
                .map(v => v.join(""));
        }
 
        console.log(qwerty("abcdbabcba".split("")));
        console.log(qwerty("ababab".split("")));
Работает чисто с массивами символов, в строки переводит только самый последний map, его можно удалить, если не нужен.
1
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
13.11.2018, 03:23
diadiavova, Lazy_Den, amr-now и снова привет
В одномерном массиве символов найти количество повторяющихся последовательностей символов с длиной больше или равной двум. Например, в строке «abcdbabcba» ответ: «ab», «bc», «abc», «ba». Не использовать строковые функции.
- https://developer.mozilla.org/... ring/slice

Мда... похоже я придрался И тем не менее slice реализован в обоих интерфейсаx - Array и String.

Пока условия выполнил только klopp
0
 Аватар для diadiavova
7258 / 2605 / 744
Регистрация: 11.04.2015
Сообщений: 4,149
Записей в блоге: 43
13.11.2018, 03:24
Qwerty_Wasd, привет.
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
https://developer.mozilla.org/ru/doc...s/String/slice
Я думаю, это нуждается в пояснении. Лично я не понял к чему эта ссылка.

Добавлено через 1 минуту
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
И тем не менее slice реализован в обоих интерфейсаx - Array и String.
Да, но слайс массива и слайс строки - это два разных слайса. Слайс массива не является строковой функцией.
0
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
13.11.2018, 03:58
diadiavova,
Цитата Сообщение от diadiavova Посмотреть сообщение
Да, но слайс массива и слайс строки - это два разных слайса. Слайс массива не является строковой функцией.
Вы ошибаетесь - https://www.ecma-international... type.slice
Цитата Сообщение от ECMAScript® 2018
NOTE 3
The slice function is intentionally generic; it does not require that its this value be an Array object. Therefore it can be transferred to other kinds of objects for use as a method.
https://www.ecma-international... type.slice
Цитата Сообщение от ECMAScript® 2018
NOTE
The slice function is intentionally generic; it does not require that its this value be a String object. Therefore it can be transferred to other kinds of objects for use as a method.
Цитата Сообщение от diadiavova Посмотреть сообщение
Я думаю, это нуждается в пояснении
Вы используете общий для Array и String метод
0
 Аватар для diadiavova
7258 / 2605 / 744
Регистрация: 11.04.2015
Сообщений: 4,149
Записей в блоге: 43
13.11.2018, 04:20
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
The slice function is intentionally generic; it does not require that its this value be an Array object. Therefore it can be transferred to other kinds of objects for use as a method.
Здесь написано, что этот метод может использовать в качестве аргумента this не только массив. Обычно это бывает полезно для объектов типа NodeList и т. п. Но как из этого можно было сделать вывод, что это то же самое, что и строковый слайс - для меня загадка. У этих методов даже сигнатуры разные, если бы это был один метод, то следующие две версии кода выводили бы одно и то же
JavaScript
1
2
        console.log(Array.prototype.slice.call("qwerty", 1, 3));
        console.log(String.prototype.slice.call("qwerty", 1, 3));
Но это не так.
Кроме того, даже если бы это было так, то это было бы не более чем вопросом внутренней реализации. Я уже не говорю о том, что в своем коде я применял этот метод исключительно к массивам.
0
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
13.11.2018, 04:38
diadiavova,
Цитата Сообщение от diadiavova Посмотреть сообщение
У этих методов даже сигнатуры разные, если бы это был один метод, то следующие две версии кода выводили бы одно и то же
Вы же слышали про полиморфизм?
Цитата Сообщение от diadiavova Посмотреть сообщение
Но как из этого можно было сделать вывод, что это то же самое, что и строковый слайс
Вы видимо не всю заметку прочитали.

Вот тут у меня вообще челюсть отпала -
JavaScript
1
2
console.log(Array.prototype.slice.call("qwerty", 1, 3));
        console.log(String.prototype.slice.call("qwerty", 1, 3));
Это Вы прочитав это
Цитата Сообщение от diadiavova Посмотреть сообщение
Therefore it can be transferred to other kinds of objects for use as a method.
, так сделали?

В заметке четко сказано, функция универсальна. То что она для разных объектов выдает разный результат, говорит лишь о том, что при реализации интерфейсов на плюсах, учтена полиморфность.

Но это все не важно, Вашу позицию я понял - переубеждать не буду. Просто учту на будущее.

Добавлено через 1 минуту
Цитата Сообщение от diadiavova Посмотреть сообщение
Я уже не говорю о том, что в своем коде я применял этот метод исключительно к массивам.
Да никто ж не спорит Просто сам факт, что этот метод делегирован и Array и String, мешает условию.

А так, если бы это была моя тема, я бы всем поставил бы по "лучший ответ".
0
 Аватар для diadiavova
7258 / 2605 / 744
Регистрация: 11.04.2015
Сообщений: 4,149
Записей в блоге: 43
13.11.2018, 04:47
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Вы же слышали про полиморфизм?
А это здесь при чем? Полиморфизм как раз подразумевает, что сигнатуры вызываемых методов одинаковы. Кроме того, полиморфный код как раз-таки предназначен для вызова разных методов в одном коде и никогда это не интерпретируется как один метод. Общая сигнатура дает возможность вызывать разные методы одним кодом, а не наоборот.
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Вы видимо не всю заметку прочитали.
Нет, я думал, что самое главное есть в цитате.
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Это Вы прочитав это
Цитата Сообщение от diadiavova Посмотреть сообщение
Therefore it can be transferred to other kinds of objects for use as a method.
, так сделали?
Нет, скорее вот это
it does not require that its this value be an Array object
Он не требует, чтобы его значение this было Массивом. Или может я неправильно перевел?
А подменить this можно с помощью call или apply, надеюсь это понятно.
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
То что она для разных объектов выдает разный результат
Слайс массива всегда выдает массив, а слайс строки всегда выдает строку.
0
Эксперт JSЭксперт HTML/CSS
2151 / 1496 / 651
Регистрация: 16.04.2016
Сообщений: 3,696
13.11.2018, 05:05
diadiavova,
Полиморфизм - возможность объектов с одинаковой спецификацией иметь различную реализацию.

JS среды для движков клиентов, реализованы на C++. Так вот при реализации абстрактных классов и интерфейсов, дабы избежать коллизий при множественном наследовании, выбирается один из трех вариантов соглашений:

1. Запрет. В одном классе запрещается реализовывать несколько интерфейсов, имеющих методы с одинаковыми сигнатурами. Если для какого-то класса требуется комбинация несовместимых интерфейсов, программист должен выбрать другой путь решения проблемы, например, выделить несколько классов, каждый из которых реализует один из необходимых интерфейсов, и использовать их экземпляры совместно.

2. Явное разрешение неоднозначности. В случае обнаружения компилятором коллизии от программиста требуется явно указать, метод какого из интерфейсов он реализует и вызывает. То есть одноимённые методы реализуются раздельно, а при вызове указывается, какой из них вызывается. При вызове одноимённых методов через переменную типа «интерфейс» неоднозначность не возникает, если использованный в качестве типа переменной интерфейс имеет только один метод с заданным именем. Вариантом этого решения является явное переименование для совпадающих по именам наследуемых или реализуемых методов, за счёт чего в пределах реализующего класса нет одноимённых методов, но при обращении через интерфейс всегда вызывается нужная реализация.

3.Общая реализация одноимённых методов. Если наследуется или реализуется несколько методов с одной и той же сигнатурой, то они объединяются в интерфейсе-наследнике, а в классе-реализаторе получают одну общую реализацию. Это хорошо подходит для случаев, когда одноимённые методы разных интерфейсов идентичны по предполагаемой функциональности, но может вызвать нежелательные эффекты, если поведение этих методов должно различаться.

Цитата Сообщение от diadiavova Посмотреть сообщение
Слайс массива всегда выдает массив, а слайс строки всегда выдает строку.
привет третий пункт.

Вот почему я удивился, когда Вы на полном серьезе, выдали мне

Цитата Сообщение от diadiavova Посмотреть сообщение
то следующие две версии кода выводили бы одно и то же
* * * *
JavaScript
1
2
console.log(Array.prototype.slice.call("qwerty", 1, 3));
* * * * console.log(String.prototype.slice.call("qwerty", 1, 3));

Цитата Сообщение от diadiavova Посмотреть сообщение
Он не требует, чтобы его значение this было объектом. Или может я неправильно перевел?
Да. Не совсем верно. "не обязательно этот переданный объект есть Array". То есть ключевое слово this не употреблялось.
0
 Аватар для diadiavova
7258 / 2605 / 744
Регистрация: 11.04.2015
Сообщений: 4,149
Записей в блоге: 43
13.11.2018, 06:09
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
Полиморфизм
Зачем все эти выкладки о разрешении коллизий в плюсах при реализации интерфейсов, содержащих методы с одинаковой сигнатурой в одном классе, когда мы говорим о методах с разной сигнатурой(тип возвращаемого значения - тоже составная часть сигнатуры), реализованных в разных классах? Каким образом это может пролить свет на обсуждаемый вопрос? Мало того, даже если один интерфейс безо всяких коллизий реализуется в разных классах, то разные реализации одного и того же метода интерфейса в разных классах не являются одним методом.
Цитата Сообщение от Qwerty_Wasd Посмотреть сообщение
не обязательно этот переданный объект есть Array
А ничего, что там this следует сразу за its? А еще по какой-то непонятной причине в спецификации слово this выделено. Для красоты наверное? Или может быть все-таки это сделали специально для того, чтобы было понятно, что это ключевое слово языка, а не просто слово из текста?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
13.11.2018, 06:09
Помогаю со студенческими работами здесь

В заданном одномерном массиве из n элементов найти количество повторяющихся чисел
В заданном одномерном массиве из n элементов найти количество повторяющихся чисел. Он выводит если например в массиве 1 1 1 3, то кол-во...

Найти количество элементов в одномерном массиве, абсолютная величина которых больше 10
Найти количество элементов в одномерном массиве, абсолютная величина которых больше 10. Можно просто нарисовать на листке схемой и...

составить программу определения числа одинаковых целых чисел к в серии длиной больше 1 в одномерном массиве Х=(х1,х2,…,хn)
type mas=array of integer; var mt,mD:mas; p,k,n,e:integer; begin write('n= '); readln(n); for p:=1 to n do readln(mt); ...

Найти количество повторяющихся последовательностей
В одномерном массиве символов найти количество повторяющихся последовательностей символов с длинной больше или равной двум.Напр. abcdbabcba...

Найти максимальную последовательность повторяющихся чисел в одномерном массиве
Вывести одномерный массив (30 элементов в интервале) и определить в нём максимальную последовательность повторяющихся чисел.


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
Восстановить юзерскрипты Greasemonkey из бэкапа браузера
damix 15.01.2026
Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes
lagorue 13.01.2026
А пригодятся-ли мне знания kubernetes в России?
Сукцессия микоризы: основная теория в виде двух уравнений.
anaschu 11.01.2026
https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/
WordPad для Windows 11
Jel 10.01.2026
WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .
Classic Notepad for Windows 11
Jel 10.01.2026
Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .
Почему дизайн решает?
Neotwalker 09.01.2026
В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3
anaschu 06.01.2026
aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR
ФедосеевПавел 06.01.2026
Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru