Палиндром

 
 
 
Сообщения:505
Простой пример, проверяющий, является ли фраза палиндромом (т.е. читается слева и справа одинаково).
Возможно задание произвольных разделителей, которые не влияют на "палиндромность" фразы.
Алгоритм, как и положено, реализован in-place.

public class Palindrom {
	private String source;
	private String delimiters;
	
	private static int NO_CHAR = -1; 

// source ,будем проверять на принадлежность палиндрому, delimiters - разделители (аналоги пробелов или сами пробелы)
	public Palindrom(String source, String delimiters) {
// будем считать, что null аналогичен пустой фразе
		this.source = (source == null) ? "" : source;
		this.delimiters = delimiters == null ? "" : delimiters;
	}

	public static void main(String[] args) {
// проверяемая фраза передается классу как параметр конструктора 
// (вообще говоря, по хорошему должна откуда-нибудь вводиться, хотя бы с клавиатуры, но пример не об этом)
// здесь передается стандартная фраза из Буратины :-), причем в качестве пробела используется сам пробел и двоеточие
// можно использовать практически неограниченное количество любых разделителей
		System.out.println("This is palindrom - "+new Palindrom("а роза упала на лапу аз;ора", "; ").isPalindrom());
	}

	public boolean isPalindrom() {
// примем считать, что пустая фраза является палиндромом
		if (source.isEmpty()) return true;
		
		boolean result = true;
// голова, бежит слева направо
		int head = 0;
// хвост, бежит справа налево
		int tail = source.length() - 1;
// ищем первый символ-не-разделитель слева
		head = findNextHead(head, tail);
		if (head == NO_CHAR) {
// так может быть, если фраза состоит из одних разделителей
           return true;
        }
// ищем первый не-разделитель справа
// он однозначно есть, иначе мы бы вернулись в предыдущем if'е
		tail = findNextTail(tail, head);
		
// голова бежит вправо навстречу хвосту, который, соответственно, бежит влево
// при этом разделители игнорируются
// из цикла выскакиваем если найдено неравенство в символах под головой и хвостом либо голова встречается с хвостом,
// то есть сравнивать больше нечего
		while (result && head < tail) {
			result = source.charAt(head) == source.charAt(tail);
			head++;
			tail--;
			head = findNextHead(head, tail);
// так может быть, если между головой и хвостом остались только символы-разделители
			if (head == NO_CHAR) return result;
			tail = findNextTail(tail, head);
		}
		
		return result;
	}

// метод ищет ближайшую к start позицию головы от положения start до положения stop, которая не будет разделителем
// другими словами, ищет первый попавшийся не-разделитель с заданной левой позиции start, но не дальше чем stop (двигаемся слева направо)
	private int findNextHead(int start, int stop) {
		int index;
		for (index = start; 
				(index <= stop) && (delimiters.indexOf(source.charAt(index)) >= 0); 
				index++);
// если символ не найден, возвращаем магический NO_CHAR, если найден, возвращаем его позицию
		return index > stop ? NO_CHAR : index;
	}

// метод ищет первый попавшийся не-разделитель с заданной правой позиции start, но не ближе чем stop (двигаемся справа налево)
	private int findNextTail(int start, int stop) {
		int index;
		for (index = start; 
				(index >= stop) && (delimiters.lastIndexOf(source.charAt(index)) >= 0); 
				index--);
// нашли - возвращаем позицию, иначе NO_CHAR
		return index < stop ? NO_CHAR : index;
	}
}

Don't think you are. Know you are.
 
 
Сообщения:7989
Хы-хы, Вы взяли простую задачку и усложнили её добавив требование in-place - забавно вышло :)

А как Вам такая - в заданной строке найти палиндром наибольшей длины. Ну например:

Quote:
Парные носки это миф? Но ежу хуже ведь красна роза упала на лапу Азора в западном самоа. Как ушаков лил во кашу какао - слыхали?


Предполагая что длина строки может быть в несколько миллионов символов и длина максимального палиндрома может быть тоже сравнимой. :-o

Извиняюсь что влез - просто однажды я сел это писать и так и не дописал, что-то медленно выходило - вот и вспомнил сейчас.

www.codeabbey.com - programming problems for novice coders (+ certificates)
 
 
Сообщения:505
RodionGork:
Вы взяли простую задачку и усложнили её добавив требование in-place - забавно вышло :)

Если без in-place, было бы слишком тривиально и не интересно :-)
RodionGork:
А как Вам такая - в заданной строке найти палиндром наибольшей длины.

Ну вот, млин...сейчас работы выше крыши, а моя работа никак не связана с программированием, и вы задачку подкидываете. Как теперь работу работать? :-)
RodionGork:
Извиняюсь что влез

Вообще говоря, именно от вас, Родион, я ожидал несколько других комментариев. Что плохо в коде/алгоритме, что совсем отвратительно. :-)
Нет, я серьезно, мне критика очень нужна (я по ней учусь :-)).

Don't think you are. Know you are.
 
 
Сообщения:505
Навскидку что-то ничего кроме банального брутфорса на ум не приходит.
Вот, собственно, сам код. Тормозной как черепаха. Случайную строку из 140000 символов считает аж 10 минут. И самое интересное, что в каждой случайной строке есть палиндром.
public class LargestPalindrom {
    private static String testString = "ssccssruurssc";
    private static String testDelimiters = " ;";

    private String source;
    private String delimiters;

    private static int NO_CHAR = -1;

    public LargestPalindrom(String source, String delimiters) {
        this.source = source == null ? "" : source;
        this.delimiters = delimiters == null ? "" : delimiters;
    }

    public static void main(String[] args) {
        for (int i = 5_000; i < 1_000_000; i += 5_000){
            System.out.println("Testing length " + i + " chars");
            // comment this to use defined test string
            testString = generateRandomTestString(i);
            // System.out.println(testString);
            long startTimeMillis = System.currentTimeMillis();
//            System.out.println("Started at " + startTimeMillis);

            LargestPalindrom palindrom = new LargestPalindrom(testString, testDelimiters);
            String longestPalindrom = palindrom.getLongestPalindrom();
            System.out.println("The longest palindrom is - " + ((longestPalindrom == null) ? "NOT FOUND" : longestPalindrom));

            long stopTimeMillis = System.currentTimeMillis();
//            System.out.println("Stopped at " + stopTimeMillis);

            System.out.println("Evaluation time " + (stopTimeMillis - startTimeMillis) + " ms");
        }
    }

    public String getLongestPalindrom() {
        if (source.isEmpty()) return null;

        PositionPair longestPositionPair = new PositionPair(0, 0);
        int leftSearchPosition = 0;
        int rightSearchPosition = source.length() - 1;

        while (leftSearchPosition < rightSearchPosition) {
            PositionPair currentPositionPair = searchFromRight(leftSearchPosition, rightSearchPosition);
            if (currentPositionPair != null) {
                if (currentPositionPair.getLength() > longestPositionPair.getLength()) {
                    longestPositionPair = currentPositionPair;
                }
            }

            leftSearchPosition++;

            currentPositionPair = searchFromLeft(leftSearchPosition, rightSearchPosition);
            if (currentPositionPair != null) {
                if (currentPositionPair.getLength() > longestPositionPair.getLength()) {
                    longestPositionPair = currentPositionPair;
                }
            }

            rightSearchPosition--;
// вот сюда можно еще кое-что добавить для оптимизации, но для худших случаев оно не поможет :-)
        }

        return longestPositionPair.getLength() > 0
                ?
                source.substring(longestPositionPair.getLeft(), longestPositionPair.getRight() + 1)
                :
                null;
    }

    private PositionPair searchFromRight(int leftPosition, int rightPosition) {
        int rightCharRunner = rightPosition;

        while (leftPosition < rightCharRunner) {
            if (isPalindrom(leftPosition, rightCharRunner)) {
                return new PositionPair(leftPosition, rightCharRunner);
            }
            rightCharRunner--;
        }
        return null;
    }

    private PositionPair searchFromLeft(int leftPosition, int rightPosition) {
        int leftCharRunner = leftPosition;

        while (leftCharRunner < rightPosition) {
            if (isPalindrom(leftCharRunner, rightPosition)) {
                return new PositionPair(leftCharRunner, rightPosition);
            }
            leftCharRunner++;
        }
        return null;
    }

    private boolean isPalindrom(int begin, int end) {
        if (begin == end) return false;

        boolean result = true;
        int head = begin;
        int tail = end;
        head = findNextHead(head, tail);
        if (head == NO_CHAR) return true;
        tail = findNextTail(tail, head);

        while (result && head < tail) {
            result = source.charAt(head) == source.charAt(tail);
            head++;
            tail--;
            head = findNextHead(head, tail);
            if (head == NO_CHAR) return result;
            tail = findNextTail(tail, head);
        }

        return result;
    }

    private int findNextHead(int start, int stop) {
        int index;
        for (index = start;
             (index <= stop) && (delimiters.indexOf(source.charAt(index)) >= 0);
             index++);
        return index > stop ? NO_CHAR : index;
    }

    private int findNextTail(int start, int stop) {
        int index;
        for (index = start;
             (index >= stop) && (delimiters.lastIndexOf(source.charAt(index)) >= 0);
             index--);
        return index < stop ? NO_CHAR : index;
    }

    private static String generateRandomTestString(int length) {
        final String alphabet = "abcdefghijklmnopqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < length; i++) {
            sb.append(alphabet.charAt((int)(Math.random() * alphabet.length())));
        }

        return sb.toString();
    }

    private class PositionPair {
        private int leftPosition;
        private int rightPosition;

        public PositionPair(int leftPosition, int rightPosition) {
            this.leftPosition = leftPosition;
            this.rightPosition = rightPosition;
        }

        public int getLength() {
            return rightPosition - leftPosition +1;
        }

        public int getLeft() {
            return leftPosition;
        }

        public int getRight() {
            return rightPosition;
        }
    }
}


В коде сделана генерация случайных срок возрастающей длины с выводом найденного палиндрома и времени расчета.
Программу можно использовать для бенчмарков и для выбора нового ника :-)
А вот вывод программы.
Testing length 5000 chars
The longest palindrom is - acoca
Evaluation time 841 ms
Testing length 10000 chars
The longest palindrom is - mofom
Evaluation time 3085 ms
Testing length 15000 chars
The longest palindrom is - xjbebjx
Evaluation time 6962 ms
Testing length 20000 chars
The longest palindrom is - yxvhvxy
Evaluation time 12355 ms
Testing length 25000 chars
The longest palindrom is - qnmmnq
Evaluation time 19283 ms
Testing length 30000 chars
The longest palindrom is - oexeo
Evaluation time 27803 ms
Testing length 35000 chars
The longest palindrom is - kararak
Evaluation time 37838 ms
Testing length 40000 chars
The longest palindrom is - zdrnrdz
Evaluation time 49657 ms
Testing length 45000 chars
The longest palindrom is - zvbfbvz
Evaluation time 62145 ms
Testing length 50000 chars
The longest palindrom is - cwrsrwc
Evaluation time 76927 ms
Testing length 55000 chars
The longest palindrom is - dmioimd
Evaluation time 91819 ms
Testing length 60000 chars
The longest palindrom is - nssqssn
Evaluation time 108868 ms
Testing length 65000 chars
The longest palindrom is - qblalbq
Evaluation time 127694 ms
Testing length 70000 chars
The longest palindrom is - pjpjpjp
Evaluation time 148066 ms
Testing length 75000 chars
The longest palindrom is - pcegecp
Evaluation time 169976 ms
Testing length 80000 chars
The longest palindrom is - btuomoutb
Evaluation time 193422 ms
Testing length 85000 chars
The longest palindrom is - fzatitazf
Evaluation time 218376 ms
Testing length 90000 chars
The longest palindrom is - hbhlhbh
Evaluation time 244878 ms
Testing length 95000 chars
The longest palindrom is - ctnjntc
Evaluation time 274093 ms
Testing length 100000 chars
The longest palindrom is - utgpgtu
Evaluation time 306774 ms
Testing length 105000 chars
The longest palindrom is - amfafma
Evaluation time 334009 ms
Testing length 110000 chars
The longest palindrom is - tlhchlt
Evaluation time 366689 ms
Testing length 115000 chars
The longest palindrom is - xxkhxhkxx
Evaluation time 399955 ms
Testing length 120000 chars
The longest palindrom is - ciqaqic
Evaluation time 435608 ms
Testing length 125000 chars
The longest palindrom is - iqqbqqi
Evaluation time 472796 ms
Testing length 130000 chars
The longest palindrom is - zgpbpgz
Evaluation time 511269 ms


З.Ы. А здесь можно спойлеры делать?

Don't think you are. Know you are.
Изменен:12 окт 2015 19:03
 
 
Сообщения:505
Не, ну а че - mofom, acoca и kararak - нормальные, стильные такие никнеймы )))

Don't think you are. Know you are.
 
 
Сообщения:79
Мне кажется, что комментарии не нужны, они только отвлекают.
Либо пишите в формате javadoc, вы же таки java-программист!
 
 
Сообщения:505
feomatr:
Либо пишите в формате javadoc

Тады надо на английском писать :-)
Не, не буду убирать, кому чистый код нужен, скопирует в IDE и комменты потрет.
Тем более, во втором примере их практически нет.
Комменты нужны, чтобы новички при желании могли въехать в алгоритм.

feomatr:
вы же таки java-программист!

Вот, к сожалению, нет :(
Я, конечно, понимаю, что некоторые товарищи, написав пару строчек кода на Java, гордо именуют себя программистами. Я пока не имею права себя так называть.
Надеюсь, что пока.

Don't think you are. Know you are.
 
 
Сообщения:7989
Quote:
Вообще говоря, именно от вас, Родион, я ожидал несколько других комментариев. Что плохо в коде/алгоритме, что совсем отвратительно. :-)

У Вас, Сергей, уже не тот уровень чтоб на таких маленьких задачах чему-то Вас можно было научить :D

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

Ну вот это:
Quote:
for (index = start;
(index <= stop) && (delimiters.indexOf(source.charAt(index)) >= 0);
index++);

конечно в реальном проекте лучше не писать, особенно в команде. Но в реальном проекте и проверку палиндрома на месте писать Вы не станете :)

А вот насчет комментов замечание резонное! Я помню :)

Quote:
Случайную строку из 140000 символов считает аж 10 минут.

А строку из 140000 одинаковых букв? Я на этом завяз... :(

www.codeabbey.com - programming problems for novice coders (+ certificates)
 
 
Сообщения:505
RodionGork:
Но в реальном проекте и проверку палиндрома на месте писать Вы не станете

Иногда пишу такую мелочевку для разминки мозга, чтоб деревом не обрастал :-)
Про уровень - как Вы это определили по паре методов? :-)

Don't think you are. Know you are.
 
 
Сообщения:7989
Quote:
Про уровень - как Вы это определили по паре методов?

Так вроде это не единственный Ваш пост на сайте :)
Quote:
cssru
Posts:114

Наблюдалась некая активность! В т.ч. по-моему вопросам касающимся веб-проектов и т.п... Я кажется после попадания на этот форум до веба только через полгода-год дошёл :D

www.codeabbey.com - programming problems for novice coders (+ certificates)
 
 
Сообщения:505
RodionGork:
Я кажется после попадания на этот форум до веба только через полгода-год дошёл :D

Согласен, на форуме я поздновато появился :-)
С вебом и спрингом познакомился только в этом январе.
И, как я обнаружил, то, что я интересуюсь вебом, еще ни разу не значит, что я хорошо знаю core.

Don't think you are. Know you are.
Изменен:13 окт 2015 04:47
 
 
Сообщения:505
RodionGork:
А строку из 140000 одинаковых букв?

Это лечится просто.
В строку 58 предыдущего примера вставляем
if ((rightSearchPosition - leftSearchPosotion) < longestPositionPair.getLength()) break;

И мы счастливы :-)

Don't think you are. Know you are.
 
Модераторы:Нет
Сейчас эту тему просматривают:Нет