51 lines
1.4 KiB
Java
51 lines
1.4 KiB
Java
import java.util.*;
|
|
public class horsePool{
|
|
static HashMap<Character, Integer> shift = new HashMap<>();
|
|
static void shiftTable(String pattern){
|
|
for(char ch = 'A'; ch<='Z';ch++)
|
|
shift.put(ch, pattern.length());
|
|
shift.put(' ', pattern.length());
|
|
for(int i =0;i<pattern.length()-1;i++)
|
|
shift.put(pattern.charAt(i), pattern.length()-1-i);
|
|
}
|
|
|
|
static int search(String text, String pattern){
|
|
int n = text.length();
|
|
int m = pattern.length();
|
|
|
|
int i = m-1;
|
|
while(i<n){
|
|
int k = 0;
|
|
while(k<m && pattern.charAt(m-1-k)== text.charAt(i-k)){
|
|
k++;
|
|
|
|
}
|
|
if(k==m){
|
|
return i-m+1;
|
|
}
|
|
i+=shift.getOrDefault(text.charAt(i), m);
|
|
}
|
|
return -1;
|
|
}
|
|
public static void main(String[] args){
|
|
Scanner sc = new Scanner(System.in);
|
|
System.out.print("\nEnter text: ");
|
|
String text = sc.nextLine().toUpperCase();
|
|
|
|
System.out.print("\nENter pattern: ");
|
|
String pattern = sc.nextLine().toUpperCase();
|
|
|
|
shiftTable(pattern);
|
|
int pos = search(text, pattern);
|
|
if(pos!=-1){
|
|
System.out.println("Pattern found at index "+ pos);
|
|
|
|
}else{
|
|
System.out.println("Pattern not found");
|
|
}
|
|
sc.close();
|
|
|
|
}
|
|
|
|
}
|