Нахождение слова, которое не является подстрокой другого слова

Question

как найти слово длины, скажем х которая не является подстрокой другого слова длины y, где

х < у? * например 1003 *

word is - apple
req word - ape
word is aaabbab
req word - aba

Answer 1

Как насчет того, чтобы начать (вероятно, медленно), но очень просто для понимания

 Generate a list of letter combinations

     a p p
     a p p l
     a p p l e
     a p l
     a p l e
     a p e
     a l e  <=== look another answer
     p p l
     p p l e
     p l e

 Test each list item to see a). whether it is a substring b) whether it is a word

Создание этого списка будет работать как рекурсивная процедура.

Answer 2

Например, вот так:

import org.testng.annotations.Test;

public class TestNotSubstring {

    public String notSubstring(String sY, int x) {
        if (sY.length() > x) {
            String sX = sY.substring(0, x - 1);
            sX = sX + (new Character((char) (sY.charAt(x)+1)).toString());
            return sX;
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < x; i++) {
                sb.append("a");
            }
            return sb.toString();
        }
    }

    @Test
    public void testApple() {
        String sY = "apple";
        String sX = notSubstring(sY, 3);
        System.out.println(sX);
        assert(!sY.contains(sX));
    }

    @Test
    public void testOrange() {
        String sY = "orange";
        String sX = notSubstring(sY, 5);
        System.out.println(sX);
        assert(!sY.contains(sX));
    }
}

Answer 3

Мне кажется, что-то вроде этого и спрашивается:

public class SubsequenceNotSubtring {
    static void subseqNotSubstring(String word, int L) {
        search(word, L, "", 0);
    }
    static void search(String word, int L, String subseq, int index) {
        if (L == 0 && !word.contains(subseq)) {
            System.out.println(subseq);
            return;
        }
        for (int i = index; i < word.length(); i++) {
            search(word, L-1, subseq + word.charAt(i), i+1);
        }
    }
    public static void main(String[] args) {
        subseqNotSubstring("apple", 3);
        subseqNotSubstring("aaabbab", 3);
    }
}

В этом списке перечислены все подпоследовательности заданной длины из заданной строки, которые не являются подстрока

Приведенный выше фрагмент кода обнаруживает следующее (аннотировано, дубликаты удалены):

apple,3   => apl, ape, ale, ppe
aaabbab,3 => aba, bbb

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

Answer 4

Я думаю, что вы хотите проверить x.length ()