Эффективно подсчитывается количество подстрок строки цифр, которые делятся на k?

Question

Нам предоставляется строка, которая состоит из цифр 0-9. Нам нужно подсчитать количество подстрок, делящихся на число k. Один из способов - сгенерировать все подстроки и проверить, делится ли он на k, но это займет O(n^2) раз. Я хочу решить эту проблему в O(n*k) времени.

1 <= n <= 100000 and 2 <= k <= 1000. 

Я видел аналогичный вопрос here. Но k был зафиксирован как 4 в этом вопросе. Итак, для решения проблемы я использовал свойство делимости на 4. Вот мое решение этой проблемы:

int main() 
{ 
    string s; 
    vector<int> v[5]; 
    int i; 
    int x; 
    long long int cnt = 0; 

    cin>>s; 
    x = 0; 
    for(i = 0; i < s.size(); i++) { 
     if((s[i]-'0') % 4 == 0) { 
      cnt++; 
     } 
    } 
    for(i = 1; i < s.size(); i++) { 
     int f = s[i-1]-'0'; 
     int s1 = s[i] - '0'; 
     if((10*f+s1)%4 == 0) { 
      cnt = cnt + (long long)(i); 
     } 
    } 
    cout<<cnt; 

} 

Но я хотел общий алгоритм для любого значения к.

Answer 1

Это действительно интересная проблема. Вместо того, чтобы прыгать в окончательный общий алгоритм, я думал, что начну с разумного алгоритма, который не совсем сократит его, а затем сделайте серию модификаций, чтобы закончить окончательный алгоритм O (nk) -time.

Этот подход сочетает в себе множество различных приемов. Основным методом является идея вычисления остатка качения по цифрам. Например, предположим, что мы хотим найти все префиксы строки, кратные k. Мы могли бы сделать это, указав все префиксы и проверив, является ли каждый из них кратным k, но это займет время не менее Θ (n), так как существует Θ (n) разных префиксов. Однако мы можем сделать это вовремя Θ (n), будучи немного более умным. Предположим, мы знаем, что мы прочитали первые h символов строки, и мы знаем оставшуюся часть числа, сформированного таким образом. Мы можем использовать это, чтобы сказать что-то о остатке первых h + 1 символов строки, так как, добавив эту цифру, мы берем существующее число, умножая его на десять, а затем добавляем в следующую цифру. Это означает, что если бы мы имели остаток от г, то наш новый остаток равен (10r + d) mod k, где d - это цифра, которую мы раскрыли.

Вот быстрый псевдокод, чтобы подсчитать количество префиксов строки, кратных k. Она работает во время Θ (п):

remainder = 0 
numMultiples = 0 
for i = 1 to n: // n is the length of the string 
    remainder = (10 * remainder + str[i]) % k 
    if remainder == 0 
     numMultiples++ 
return numMultiples 

Мы будем использовать этот первоначальный подход в качестве строительного блока для общего алгоритма.

Итак, теперь у нас есть алгоритм, который может найти число префиксов нашей строки, кратными k. Как мы можем преобразовать это в алгоритм, который находит количество подстрок , которые являются кратными k? Начнем с подхода, который не совсем работает. Что, если мы посчитаем все префиксы исходной строки, кратные k, затем опустим первый символ строки и подсчитаем префиксы того, что осталось, затем опустим второй символ и подсчитаем префиксы того, что осталось, и т. Д.? В конце концов это найдет каждую подстроку, поскольку каждая подстрока исходной строки является префиксом некоторого суффикса строки.

Вот некоторый грубый псевдокод:

numMultiples = 0 
for i = 1 to n: 
    remainder = 0 
    for j = i to n: 
     remainder = (10 * remainder + str[j]) % k 
     if remainder == 0 
      numMultiples++ 
return numMultiples 

К примеру, работает этот подход на строке 14917 ищет кратные 7 повернется вверх эти строки:

• Струнных 14917: Находит 14, 1491 , 14917
• Строка 4917: Находки 49,
• Строка 917: Находит 91, 917
• Строка 17: ничего не находит
• Строка 7: Находит 7

Хорошая новость об этом подходе является то, что он найдет все подстроки, которые работают , Плохая новость заключается в том, что она работает во времени Θ (n).

Но давайте посмотрим на строки, которые мы видим в этом примере. Посмотрите, например, на подстроки, найденные поиском префиксов всей строки. Мы обнаружили три из них: 14, 1491 и 14917. Теперь посмотрим на «различия» между этими строками:

• Разница между 14 и 14917 является 917.
• Разница между 14 и 1491 является 91
• Разница между 1491 и 14917 является 7.

Обратите внимание, что разница в каждой из этих строк сам по себе является подстрока 14917 это кратна 7, и в самом деле, если вы посмотрите на другие строки, которые мы совпавших позже в пробеге алгоритма Я найду эти другие строки.

Это не случайно. Если у вас есть два числа с общим префиксом, кратным одному числу k, то «разница» между ними также будет кратной k. (Это хорошее упражнение, чтобы проверить математику на этом.)

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

Прежде всего, предположим, что мы находим r различных префиксов строки, кратных k. Сколько общих подстрок мы нашли, если бы включили различия? Ну, мы нашли k строк, а также одну дополнительную строку для каждой (неупорядоченной) пары элементов, которая работает с k + k (k-1)/2 = k (k + 1)/2 обнаруженных общих подстрок.Тем не менее, нам все равно нужно убедиться, что мы не делаем ничего счёта.

Чтобы узнать, не будем ли мы что-то считать, мы можем использовать следующую технику. Когда мы вычисляем катящиеся остатки вдоль строки, мы будем хранить остатки, которые мы найдем после каждой записи. Если в процессе вычисления остатка в качении мы заново открываем остаток, который мы уже вычислили в какой-то момент, мы знаем, что работа, которую мы делаем, избыточна; то предыдущее сканирование по строке уже рассчитало бы этот остаток, и все, что мы обнаружили с этого момента, будет уже найдено.

Подставив эти идеи вместе дает нам этот псевдокод:

numMultiples = 0 
seenRemainders = array of n sets, all initially empty 
for i = 1 to n: 
    remainder = 0 
    prefixesFound = 0 
    for j = i to n: 
     remainder = (10 * remainder + str[j]) % k 
     if seenRemainders[j] contains remainder: 
      break 
     add remainder to seenRemainders[j] 
     if remainder == 0 
      prefixesFound++ 
    numMultiples += prefixesFound * (prefixesFound + 1)/2 
return numMultiples 

Так, насколько эффективно это? На первый взгляд это похоже на то, что он работает во времени O (n) из-за внешних циклов, но это не плотная привязка. Обратите внимание, что каждый элемент может быть передан только во внутреннем цикле не более k раз, так как после этого нет никаких остатков, которые все еще свободны. Поэтому, поскольку каждый элемент посещается не более O (k) раз и содержит n общих элементов, среда выполнения O (nk), которая соответствует вашим требованиям времени выполнения.