adapted to new storage location
[feisty_meow.git] / 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 }