0

Здравствуйте! Недавно получил задание: Написать реализацию функции: Int pos(String search, String where); Где: search - искомая строка, where - где ищем. Функция возвращает позицию строки search в строке where или -1, если вхождение не найдено. Строку считать массивом Char(индексация от 0). Char между собой можно сравнивать. У строки есть только метод length(), других методов нет.

Прошу помощи у более опытных. Решил сперва с помощью indexOf(), но естественно ответ не был засчитан. Также думал, что нужно сравнить длину строки search с длинами элементов массива where, но вот как это вылить в синтаксис java не приходит в голову.

Не обязательно писать весь код, можно привести аналогию, направить по ссылкам к похожим задачам.

Спасибо!

8
  • А почему просто поэлементо не сравнить?
    – s8am
    16 авг 2016 в 18:38
  • скорее всего предполагается использование charAt
    – Russtam
    16 авг 2016 в 18:56
  • нет, без charAt'а
    – e18718
    16 авг 2016 в 19:02
  • вы вхождение с одним length() не найдете, да и зачем в задании были бы фразы "Строку считать массивом Char(индексация от 0)"?
    – Russtam
    16 авг 2016 в 19:04
  • а также ,цитирую "У строки есть только метод length(), других методов нет." Изменять условия задачи не могу, как бы не хотелось. Это один из первых методов, который мне выдал гугл, в т.ч. и indexOf(), который был отклонен.
    – e18718
    16 авг 2016 в 19:17

3 ответа 3

1

Напишу вариант со сравнением посимвольно, т.к. в задании скорее всего опечатка и только с одним length() его сделать невозможно.

public static int pos(String search, String where) {
    //искомая строка должна быть не больше той, в которой ищем
    if (search.length() > where.length()) {
        return -1;
    }
    //ищем только до определенной позиции, т.к. дальше искомая строка уже не "влезет"
    for (int i = 0; i < where.length() - search.length() + 1; i++) {
        // если совпадает первый символ ...
        if (where.charAt(i) == search.charAt(0)) {
            boolean found = true;
            // ... то сверим все остальные
            for (int j = i + 1; j < i + search.length(); j++) {
                // если хоть один не совпадает ...
                if (where.charAt(j) != search.charAt(j - i)) {
                    // ... значит не нашли
                    found = false;
                    break;
                }
            }
            // если все символы совпали
            if (found) {
                //значит нашли и возвращаем позицию
                return i;
            }
        }
    }
    //ничего не нашли
    return -1;
}
2
  • спасибо большое! не будет ли наглостью если попрошу вас добавить комментарии?
    – e18718
    16 авг 2016 в 19:39
  • Вы были правы, задача составлена не корректно!
    – e18718
    16 авг 2016 в 20:15
1

Алгоритм Кнута — Морриса — Пратта, взят отсюда алгоритм

public static int[] indexesOf(char[] pattern, char[] text) {
        int[] pfl = pfl(pattern);
        int[] indexes = new int[text.length];
        int size = 0;
        int k = 0;
        for(int i = 0; i < text.length; ++i) {
            while(pattern[k] != text[i] && k > 0) {
                k = pfl[k - 1];
            }
            if(pattern[k] == text[i]) {
                k = k + 1;
                if(k == pattern.length) {
                    indexes[size] = i + 1 - k;
                    size += 1;
                    k = pfl[k - 1];
                }
            } else {
                k = 0;
            }
        }
        return Arrays.copyOfRange(indexes, 0, size);
    }

    public static int[] pfl(char[] text) {
        int[] pfl = new int[text.length];
        pfl[0] = 0;
        for(int i = 1; i < text.length; ++i) {
            int k = pfl[i - 1];
            while(text[k] != text[i] && k > 0) {
                k = pfl[k - 1];
            }
            if(text[k] == text[i]) {
                pfl[i] = k + 1;
            } else {
                pfl[i] = 0;
            }
        }
        return pfl;
    }

как использовать

     String s2 = "ее";
     String s1 = "ццццццццццццццееццццуувыфывфыв";

        int[] answer = indexesOf(s2.toCharArray() , s1.toCharArray());


        for(int q : answer) {
            System.out.println(q);  //  14
        }

Массив содержит все позиции схожих подстрок, но она одна и равна 14

1
  • Благодарю! Возможно данный метод и является решением, но для моего понимания он на данный момент сложен, словно решение квадратного уравнения с отрицательным корнем с помощью комплексных чисел для ученика 8-го класса.
    – e18718
    16 авг 2016 в 20:30
0

поиск делаешь в цикле от нуля до длины where - длина search делаешь substring из where длиной search и сравниваешь с search и так итерация по шагово со сдвигом на один символ функцию substring если использовать внешнею нельзя то достаточно легко самому написать :)

for (int i=0; i < where.length() - search.length(); i++){ 
  if (substring(search, i, where.length()) == search) { 
    return i; 
  }
}
4
  • не совсем понял, что вы написали. for(int i=0; i<where.length(); i++){ search.length() = where.substring(search.length(i)); } ?
    – e18718
    16 авг 2016 в 19:13
  • for (int i=0; i < where.length() - search.length(); i++){ if (substring(search, i, where.length()) == search) { return i; }}
    – plesser
    16 авг 2016 в 19:16
  • Если substring можно использовать то соотвественно where.substr(i, search.length());
    – plesser
    16 авг 2016 в 19:19
  • строка, а именно логическое выражение if (substring(search, i, where.length()) == search) мне непонятна, т.к. еще до этого раздела джавы я еще видимо не дошел. Напишите пожалуйста,что за тема.
    – e18718
    16 авг 2016 в 19:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.