Программа для поиска номера «а» в строке, которая повторяется n символов?

Question

Я пишу программу, чтобы найти число «а» в данной строке, которая повторяется. Например, вызов findAmountA («aba», 7) означает, что он находит число «a» в строке «aba», повторенное для 7 символов. Таким образом, «abaabaa» является последней строкой, поэтому вызов вернет 5.

Без фактического создания строки из 7 символов (поэтому вызовы для 1 000 000 символов не заняли бы так много времени), как бы я использовал математику для выполнения этой задачи? Я не могу продвинуться дальше, чем это, поскольку я пытался устранить это некоторое время.

Имейте в виду, что я начинающий программист на Java (студент) и не хочу использовать какой-либо сложный / необычный синтаксис, который я бы не изучал в старшей школе. Спасибо!

public class AInString {
    public static void main(String[] args) {
        boolean a = findAmountA("aba", 10) == 7;
        boolean b = findAmountA("a", 100) == 100;
        boolean c = findAmountA("abca", 10) == 5;
        boolean d = findAmountA("", 10) == 0;
        boolean e = findAmountA("abcaa", 1000000) == 600000;
        boolean f = findAmountA("abc", 0) == 0;
        boolean g = findAmountA("bcd", 10) == 0;
        System.out.println(a && b && c && d && e && f && g);
    }
    public static int findAmountA(String word, int n) {
        String s = word;
        if(s.length() == 0 || aInWord(word) == 0) {
            return 0;
        }else {
            int a = (aInWord(s));
            return a;
        }
    }
    public static int aInWord(String word) {
        String s = word;
        int aInWord = 0;
        for(int i = 0; i < word.length(); i++) {
            if(s.charAt(i) == 'a') {
                aInWord++;
            }
        }
        return aInWord;
    }

}

Answer 1

Спасибо всем за помощь, с помощью подстрок я нашла ответ:

public class AInString {
    public static void main(String[] args) {
        boolean a = findAmountA("aba", 10) == 7;
        boolean b = findAmountA("a", 100) == 100;
        boolean c = findAmountA("abca", 10) == 5;
        boolean d = findAmountA("", 10) == 0;
        boolean e = findAmountA("abcaa", 1000000) == 600000;
        boolean f = findAmountA("abc", 0) == 0;
        boolean g = findAmountA("bcd", 10) == 0;
        System.out.println(a && b && c && d && e && f && g);
    }
    public static int findAmountA(String word, int n) {
        String s = word;
        if(s.length() == 0 || aInWord(s) == 0) {
            return 0;
        }else {
            int a = aInWord(s)*(n/s.length());
            int b = n % s.length();
            return a + aInWord(s.substring(0, b));
        }
    }
    public static int aInWord(String word) {
        String s = word;
        int aInWord = 0;
        for(int i = 0; i < word.length(); i++) {
            if(s.charAt(i) == 'a') {
                aInWord++;
            }
        }
        return aInWord;
    }

}

Answer 2

Я сделал некоторые изменения в вашем коде, посмотрите:

public static void main(String[] args) {
    int a = findAmountA("aba", 10); // 7
    int b = findAmountA("a", 100); // 100;
    int c = findAmountA("abca", 10); //5;
    int d = findAmountA("", 10); //0;
    int f = findAmountA("abc", 0); //0;
    int g = findAmountA("bcd", 10); //0;
    System.out.println(a + " " + b + " " + c + " " + d + " " + f + " " + g);
}

public static int findAmountA(String word, int n) {
    if (word.length() < n) {
        for (int i=0; i<word.length(); i++) {
            while (word.length() < n) {
                word = word + word.charAt(i);
                break;
            }
        }
    } else if (word.length() > n) {
        for (int i=0; i<word.length(); i++) {
            word = word.substring(0, n);
        }
    } else {
        return aInWord(word);
    }
    return aInWord(word);
}

public static int aInWord(String word) {
    String s = word;
    int aInWord = 0;
    for(int i = 0; i < word.length(); i++) {
        if(s.charAt(i) == 'a') {
            aInWord++;
        }
    }

Answer 3

Теперь, когда вы посчитали вхождения в символ a в строке word, вы можете подсчитать вхождения этого символа в расширенной строке n символов:

return n / word.length() * aInWord(word) + aInWord(word.substring(0, n % word.length()));

n / word.length() дает количество полных повторов строки, которые вписываются в n.Умножение этого числа на aInWord(word) дает счет a в повторениях word, которые точно укладываются в n.

Остальное - это определение количества повторов в подстроке word, которая не вписывается в n, с помощью оператора модуля % для определения размера частичной подстроки (если есть)При сложении двух отсчетов вместе получается общее количество вхождений в расширенной строке.

Вот чистая версия, которая позволяет избежать дублирования переменных, дополнительных условий и обобщает методы для максимального повторного использования:

class Main {
    public static void main(String[] args) {
        assert findAmount("aba", 10, "a") == 7;
        assert findAmount("a", 100, "a") == 100;
        assert findAmount("abca", 10, "a") == 5;
        assert findAmount("", 10, "a") == 0;
        assert findAmount("abcaa", 1000000, "a") == 600000;
        assert findAmount("abc", 0, "a") == 0;
        assert findAmount("bcd", 10, "a") == 0;
        System.out.println("tests passed");
    }

    public static int findAmount(String word, int n, String target) {
        if (word.length() == 0) {
            return 0;
        }

        return n / word.length() * count(target, word) + 
               count(target, word.substring(0, n % word.length()));
    }

    public static int count(String target, String s) {
        return s.length() - s.replace(target, "").length();
    }
}

Попробуйте!

Answer 4

Разделите целевую длину на длину ввода: для примера:

7 / 3 = 2 remainder 1

2 количество «полных копий» всей входной строки, которое вы будете использовать. Итак, найдите число «a» во всей строке, умножьте на 2.

Вы возьмете первый 1 символ ввода, чтобы составить остаток из 7 символов. Подсчитайте количество «а» в этой подстроке.

Просто сложите эти два числа вместе.

int total = count(input, "a") * targetLength / input.length()
          + count(input.substring(0, targetLength % input.length()), "a");

, где count(input, c) - это некоторый метод подсчета количества вхождений c в input.

Answer 5

Допустим, ваша короткая строка w содержит N копий 'a'. Тогда результирующая строка будет состоять из K копий w с последующей пустой строкой «tail».

Значение K можно определить путем целочисленного деления числа 'a' s в целевой строке на N. Тогда число t из 'a' s в «хвосте» будет равно остатку подразделения. Теперь вы можете распечатать K копий w с последующим кратчайшим префиксом 'w', содержащим t 'a' с.