001package algs53; // section 5.3
002import stdlib.*;
003/* *************************************************************
004 *
005 *  Compilation:  javac Brtue.java
006 *  Execution:    java Brute pattern text
007 *
008 *  Reads in two strings, the pattern and the input text, and
009 *  searches for the pattern in the input text using brute force.
010 *
011 *  % java Brute abracadabra abacadabrabracabracadabrabrabracad
012 *  text:    abacadabrabracabracadabrabrabracad
013 *  pattern:               abracadabra
014 *
015 *  % java Brute rab abacadabrabracabracadabrabrabracad
016 *  text:    abacadabrabracabracadabrabrabracad
017 *  pattern:         rab
018 *
019 *  % java Brute rabrabracad abacadabrabracabracadabrabrabracad
020 *  text:    abacadabrabracabracadabrabrabracad
021 *  pattern:                        rabrabracad
022
023 *
024 *  % java Brute bcara abacadabrabracabracadabrabrabracad
025 *  text:    abacadabrabracabracadabrabrabracad
026 *  pattern:                                   bcara
027 *
028 *  % java Brute abacad abacadabrabracabracadabrabrabracad
029 *  text:    abacadabrabracabracadabrabrabracad
030 *  pattern: abacad
031 *
032 ***************************************************************/
033
034public class XBrute {
035
036        /* *************************************************************************
037         *  String versions
038         ***************************************************************************/
039
040        // return offset of first match or N if no match
041        public static int search1(String pat, String txt) {
042                int M = pat.length();
043                int N = txt.length();
044
045                for (int i = 0; i <= N - M; i++) {
046                        int j;
047                        for (j = 0; j < M; j++) {
048                                if (txt.charAt(i+j) != pat.charAt(j))
049                                        break;
050                        }
051                        if (j == M) return i;            // found at offset i
052                }
053                return N;                            // not found
054        }
055
056        // return offset of first match or N if no match
057        public static int search2(String pat, String txt) {
058                int M = pat.length();
059                int N = txt.length();
060                int i, j;
061                for (i = 0, j = 0; i < N && j < M; i++) {
062                        if (txt.charAt(i) == pat.charAt(j)) j++;
063                        else { i -= j; j = 0;  }
064                }
065                if (j == M) return i - M;    // found
066                else        return N;        // not found
067        }
068
069
070        /* *************************************************************************
071         *  char[] array versions
072         ***************************************************************************/
073
074        // return offset of first match or N if no match
075        public static int search1(char[] pattern, char[] text) {
076                int M = pattern.length;
077                int N = text.length;
078
079                for (int i = 0; i <= N - M; i++) {
080                        int j;
081                        for (j = 0; j < M; j++) {
082                                if (text[i+j] != pattern[j])
083                                        break;
084                        }
085                        if (j == M) return i;            // found at offset i
086                }
087                return N;                            // not found
088        }
089
090        // return offset of first match or N if no match
091        public static int search2(char[] pattern, char[] text) {
092                int M = pattern.length;
093                int N = text.length;
094                int i, j;
095                for (i = 0, j = 0; i < N && j < M; i++) {
096                        if (text[i] == pattern[j]) j++;
097                        else { i -= j; j = 0;  }
098                }
099                if (j == M) return i - M;    // found
100                else        return N;        // not found
101        }
102
103
104        // test client
105        public static void main(String[] args) {
106                //args = new String[] { "abracadabra", "abacadabrabracabracadabrabrabracad" };
107                //args = new String[] { "rab",         "abacadabrabracabracadabrabrabracad" };
108                //args = new String[] { "bcara",       "abacadabrabracabracadabrabrabracad" };
109                //args = new String[] { "rabrabracad", "abacadabrabracabracadabrabrabracad" };
110                args = new String[] { "abacad",      "abacadabrabracabracadabrabrabracad" };
111                String pat1 = args[0];
112                String txt1 = args[1];
113                char[] pat2 = pat1.toCharArray();
114                char[] txt2 = txt1.toCharArray();
115
116                int offset1a = search1(pat1, txt1);
117                int offset2a = search2(pat1, txt1);
118                int offset1b = search1(pat2, txt2);
119                int offset2b = search2(pat2, txt2);
120
121                // print results
122                StdOut.println("text:    " + txt1);
123
124                // from brute force search method 1a
125                StdOut.print("pattern: ");
126                for (int i = 0; i < offset1a; i++)
127                        StdOut.print(" ");
128                StdOut.println(pat1);
129
130                // from brute force search method 2a
131                StdOut.print("pattern: ");
132                for (int i = 0; i < offset2a; i++)
133                        StdOut.print(" ");
134                StdOut.println(pat2);
135
136                // from brute force search method 1b
137                StdOut.print("pattern: ");
138                for (int i = 0; i < offset1b; i++)
139                        StdOut.print(" ");
140                StdOut.println(pat1);
141
142                // from brute force search method 2b
143                StdOut.print("pattern: ");
144                for (int i = 0; i < offset2b; i++)
145                        StdOut.print(" ");
146                StdOut.println(pat2);
147        }
148}