Trouver un mot qui n'est pas une sous-chaîne d'un autre mot

Question

comment peut-on trouver un mot de longueur x dire qui n'est pas une sous-chaîne d'un autre mot de longueur y, où

x < y? par exemple

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

Answer 1

Je crois que quelque chose de ce genre est ce qui demande:

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); 
    } 
} 

cette liste tous subsequences de une longueur donnée d'une chaîne donnée qui n'est pas substrings.

L'extrait ci-dessus trouve les suivants (annotés, enlevés): dupes

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

Il convient de noter que cet algorithme est la force brute naïve et a horreur de la complexité asymptotique. De meilleurs algorithmes avec une structure de données de chaîne plus sophistiquée pourraient certainement être concoctés si nécessaire. La direction la plus prometteuse serait d'utiliser un suffix tree.

Answer 2

Je pense que vous voulez vérifier x.length() < y.length() et y.indexOf (x) == - 1

Answer 3

Comme ce par exemple:

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 4

Que diriez-vous de commencer par faire le (probablement lent) mais très simple à comprendre

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 

Génération cette liste fonctionnerait bien comme une routine récursive.