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

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

11.11.2018, 23:55. Показов 8839. Ответов 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,150
Записей в блоге: 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,150
Записей в блоге: 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,150
Записей в блоге: 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,150
Записей в блоге: 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,150
Записей в блоге: 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,150
Записей в блоге: 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,150
Записей в блоге: 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
Ответ Создать тему
Новые блоги и статьи
Символьное дифференцирование
igorrr37 13.02.2026
/ * Логарифм записывается как: (x-2)log(x^2+2) - означает логарифм (x^2+2) по основанию (x-2). Унарный минус обозначается как ! */ #include <iostream> #include <stack> #include <cctype>. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL3_image
8Observer8 10.02.2026
Содержание блога Библиотека SDL3_image содержит инструменты для расширенной работы с изображениями. Пошагово создадим проект для загрузки изображения формата PNG с альфа-каналом (с прозрачным. . .
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce
volvo 10.02.2026
В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru