Подсчет вхождений буквы в бесконечной строке

Question

У меня есть следующая строка с именем s="abcac", которая повторяется бесконечно много раз. Это означает, что s будет выглядеть следующим образом: s="abcacabcacabcacabcacabcac...." и n представляет подстроку s.

Например, если s="monday" и n="10", подстрока, которую мы рассматриваем, будет finalString="mondaymond", поскольку бесконечная строка будет "mondaymondaymondaymonday...", а первые 10 символов s будут "mondaymond"

Я пытаюсь посчитать вхождения буквы «а» в finalString. Этот код работает правильно, однако, когда n> 1000000, программа не будет работать.

Кроме того, если я изменю n с int на long, цикл for не будет работать в этом случае.

Каково было бы решение этой проблемы?

public static void main(String[] args){

            String s="abcac";
            int aCount=0;
            int n=1000;
            int j=0;


            char[] sCharArray=s.toCharArray();

            char[] finalString = new char[n];

            for(int i=0;i<n;i++){

                if(j==s.length())
                    j=0;

                finalString[i]=sCharArray[j];
                j++;


            }


            for(int i=0; i<n;i++){
                if(finalString[i]=='a')
                    aCount++;
            }


    System.out.println(aCount);

            }

Answer 1

Вам не нужно создавать свою последнюю строку. Вы просто должны посчитать вхождения 'a' (или что хотите) в строке s и посчитать, сколько раз этот s повторяется. И в конце концов, посчитайте вхождения в напоминании буквой «а».

long countInS = // count all occurances of 'a'
long repeats = n / s.length;
long reminder = n % s.length;
String sReminder = s.substring(reminder);
long countInReminder = // count all occurances of 'a' in sReminder 
long count = repeats * countInS + countInReminder;

не нужно тратить свою оперативную память

Answer 2

Как уже указывалось в других ответах, вам не нужно создавать свою окончательную строку.

Вот мое решение:

public static void main(String[] args){
    String s = "abcacas";
    long n = 1000000;

    long count = getCount(s, n, 'a');
    System.out.println(count);
}

private long getCount(String str, long n, char c) {
    int length = str.length();

    long repeats = n / length;
    long reminder = n % length;

    long count = 0;
    for (int i = 0; i < length; i++) {
        if (str.charAt(i) == c) {
            count += repeats;
            if (i < reminder) {
                count++;
            }
        }
    }
    return count;
}

Answer 3

Я предлагаю выяснить, сколько раз повторяется базовая строка, и вычислить вхождения буквы, используя эту информацию, плюс количество вхождений дополнительной подстроки в самом конце. Например:

String s = "monday";
int n = 10;
String chr = "a";

int baseNum = s.length() - s.replace(chr, "").length();
int baseCnt = (n / s.length()) * baseNum;
int index = n % s.length();
String left = s.substring(0, index);
int finalCnt = left.length() - left.replace(chr, "").length();
int totalCnt = baseCnt + finalCnt;

System.out.println("There were " + totalCnt + " letter " + chr + ".");

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