Как эффективно создать «бесконечную» строку?

Question

[Георгий]

Всем привет.
Суть задачи в том, что дана строка str, индекс начала которой надо найти в другой строке numbers.
Строка numbers имеет вид: "12345678910", то бишь числа по возрастанию.
Допустим, str = "123", значит вывести надо 0.
Но если str равен, например, "15", то мы все равно должны найти правильный индекс (то есть, как я понимаю, превратить numbers в "123456789101112131415..."
Саму задачу я выполнить могу, но работает она слишком медленно. Уже второй день пытаюсь оптимизировать, но лучшее, что получилось, ниже.
Кто может подсказать что-либо? Программирую не так давно, поэтому мог написать полную чушь.
Примеры входных и выходных значений:
str = "456", выходные данные = 3.
str = "454", выходные данные = 79;
str = "99100", выходные данные = 187;
str = "123456798", выходные данные = 1000000071 (вот здесь я даже не могу получить результат, потому что очень долго выполняется).

static long findPosition(string str) {
    StringBuilder numbers = new StringBuilder("12345678910");
    BigInteger i = 10;
    StringBuilder temp = new StringBuilder(1000);

    // FindSubstring - алгоритм Кнутта-Морриса-Пратта для поиска индекса
    while (FindSubstring(str, numbers.ToString()) == -1) {
        // Здесь я часто менял "j < 100" на что-то другое, для разных значений скорость изменяется
        for (int j = 0; j < 100; j++) {
            // Здесь так же я менял на добавление большего количеств чисел, скорость тоже значительно увеличивалась, но 
            // но все равно программа работает медленно
            temp.AppendFormat("{0}{1}{2}{3}{4}{5}{6}{7}{8}{9}", i + 1, i + 2, i + 3, i + 4, i + 5, i + 6, i + 7, i + 8, i + 9, i + 10);
            i += 10;
        }
        numbers.Append(temp);
        temp.Clear();
    }

    return FindSubstring(str, numbers.ToString());
}

Comments

[Лежебокер]

Какова вообще цель?

[Георгий]

EnDeRJaY: Попалась такая задача, хочу решить. Очень "зацепило" почему-то, программирую недавно и в первый раз такое испытываю, даже уснуть не мог нормально.

[Лежебокер]

Георгий: Какой должен быть конечный результат и зачем нужно число заходящее за триллион?

[Георгий]

EnDeRJaY: Собственно сама задача с codewars.com. Такое число один из тестов там. Но прошу помощи не для того, чтобы "сдать" её на сайте, а хочу разобраться.

[Лежебокер]

Георгий: Строка numbers, а именно число весит 1,5 ГБ(мне так сказал калькулятор, но он скорее всего врёт).Естественно он медленно работает.

Answer 1

[longclaps]

Суть задачи в том, чтобы вычислить индекс, не создавая строку numbers. Быстро и не пожирая память.

Comments

[Георгий]

Такой вариант я тоже рассматривал, но никак не получилось реализовать что-то подобное.

[longclaps]

Георгий: Ну давайте попробуем еще раз.
Возьмем для простоты конкретный пример - число 767867
Первый заход - пробуем разбить число на группы из одной цифры и смотрим, не цепочка ли это из возрастающих чисел: 7~6~7~8~6~7 - нет
Второй заход - пробуем разбить число на группы из 2 цифр, тут уже 2 варианта
76~78~67 - нет
7~67~86~7 - на края мы даже не смотрим, серёдка не бьёт
Третий заход - 3 варианта
767~867 - нет
7~678~67 - вутренних противоречий не выявлено (в середке одно число, не с чем сопоставлять)
76~786~7 - вутренних противоречий не выявлено
разбираем подробнее
7~678~67 => хорошо бы (678-1)~678~(678+1)==677~678~679, голова подходит, хвост подходит
76~786~7 => хорошо бы (786-1)~786~(786+1)==785~786~787, ни голова ни хвост не подходят
Всё, надо посчитать индекс вхождения числа(!) 678 и что-то там вычесть.
До 678 встречаются все однозначные числа - 9штук*1цифра, все двузачные (от 10 до 99 - 90штук*2цифры) и (677-99)*3цифры.

[Георгий]

longclaps: Огромное спасибо, буду пробовать.

[longclaps]

Георгий:
В разборе упущен такой, например, вариант: 79899100101 -> 97~98~99~100~101
Чтобы не усложнять жизнь, можно так переделать метод:
не разбиваем всё число на двузначные группы, а выбираем лишь первую - в этом случае 98 - и продолжаем её вправо и влево арифм. прогрессией.

Answer 2

[xmoonlight]

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

Comments

[Лежебокер]

>Программирую не так давно, поэтому мог написать полную чушь.
Допустим.
>1. Вначале - нужно составить формулу повышения разрядности позиций в зависимости от входа.
2. Затем - спозиционировать рекурсивно начиная со старшего разряда - вглубь.
3. Все прыжки - просуммировать и получите позицию.
Это ты написал для новичка?

[xmoonlight]

EnDeRJaY: я написал, чтобы дать понимание последовательности действий.
Для кого: написал для всех.
Если человек решил брать задачи подобной сложности для самоутверждения - я не виноват: хозяин - барин!

Answer 3

[Сергей]

Конечно аналитически найти индекс это true path, но сделать "в лоб" тоже можно. Для str = "123456798" ответ получишь через 3 минуты :)

using System;
using System.Collections.Generic;
using System.Linq;

namespace FindString
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = "123456798";
            string buf = string.Concat(Generator.All().Take(str.Length));

            ulong index = 0;
            foreach (var c in Generator.All().Skip(str.Length))
            {
                if (buf == str)
                {
                    break;
                }

                buf = buf.Substring(1) + c;
                ++index;
            }

            Console.WriteLine("index is {0}", index);
            Console.ReadKey();
        }
    }

    public class Generator
    {
        public static IEnumerable<char> All()
        {
            ulong v = 0;
            while(true)
            {
                ++v;
                foreach(var c in v.ToString().ToCharArray())
                {
                    yield return c;
                }
            }
        }
    }
}