kona/src/org/feistymeow/algorithms/SubstringFinder.java

   1 package org.feistymeow.algorithms;
   2
   3 /**
   4  * used to find strings in other strings.
   5  *
   6  * part of google interview prep.
   7  */
   8
   9 public class SubstringFinder
  10 {
  11
  12         /**
  13          * returns the position of 'x' in 'y', or returns a negative number.
  14          */
  15         public int findXinY(String x, String y)
  16         {
  17                 if ((x == null) || (y == null))
  18                         return -1; // nulls are invalid to compare.
  19                 if (y.length() < x.length())
  20                         return -1; // x cannot be found in shorter string.
  21                 for (int yIter = x.length() - 1; yIter < y.length(); yIter++) {
  22                         boolean good = true;
  23                         /*
  24                          * xIter has to start at valid value in x, and that needs to be at end of x. board actually had uncorrected error here, where
  25                          * xIter started at yIter, which is really wrong.
  26                          */
  27                         // simplified xIter which was inducing all sorts of OBOBs. even though i found the end in yIter,
  28                         // i go forwards on xIter.
  29                         for (int xIter = 0; xIter < x.length(); xIter++) {
  30                                 int yComparePosition = (yIter - x.length() + 1) + xIter;
  31                                 if (x.charAt(xIter) != y.charAt(yComparePosition)) {
  32                                         // System.out.println("no match -- y[" + yIter + "]=" + y.charAt(yPosn) + " x[" + xIter + "]=" + x.charAt(xIter));
  33                                         good = false;
  34                                         break;
  35                                 }
  36                         }
  37                         if (good) {
  38                                 int toReturn = yIter - x.length() + 1;
  39                                 // System.out.println("found at position " +toReturn );
  40                                 return toReturn;
  41                         }
  42                 }
  43
  44                 return -1;
  45         }
  46
  47         public static void main(String[] argv)
  48         {
  49                 SubstringFinder sf = new SubstringFinder();
  50
  51                 String x1 = "petunia";
  52                 String y1 = "sometimes my flowers are roses and sometimes they are petunias and sometimes they are turnips.";
  53                 if (sf.findXinY(x1, y1) != 54) {
  54                         System.out.println("FAILURE: did not find at right index for test 1");
  55                 } else {
  56                         System.out.println("OKAY: found substring at right index for test 1");
  57                 }
  58
  59                 String x2 = "qn";
  60                 String y2 = "xaqno";
  61                 if (sf.findXinY(x2, y2) != 2) {
  62                         System.out.println("FAILURE: did not find at right index for test 2");
  63                 } else {
  64                         System.out.println("OKAY: found substring at right index for test 2");
  65                 }
  66
  67                 String x3 = "qn";
  68                 String y3 = "xaqon";
  69                 if (sf.findXinY(x3, y3) >= 0) {
  70                         System.out.println("FAILURE: found non-existent string for test 3");
  71                 } else {
  72                         System.out.println("OKAY: did not find substring for test 3");
  73                 }
  74
  75         }
  76 }