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}