Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- package acm;
- import java.io.BufferedReader;
- import java.io.IOException;
- import java.io.InputStreamReader;
- import java.util.ArrayList;
- public class BigStringSearch {
- public static void main(String[]args) throws IOException {
- ArrayList<TestCase> al=new ArrayList<TestCase>();
- BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
- String cases=br.readLine();
- while(al.size()<Integer.parseInt(cases)){
- TestCase tc=new TestCase();
- tc.setId(al.size()+1);
- String ptn=br.readLine();
- tc.setPattern(ptn);
- String txt=br.readLine();
- tc.setText(txt);
- al.add(tc);
- }
- for(int i=0;i<al.size();i++){
- TestCase tc=(TestCase)(al.get(i));
- int index=horsPool(tc.getPattern(),tc.getText());
- if(index==-1){
- System.out.println(tc.getId()+" "+"NOT FOUND");
- }else{
- System.out.println(tc.getId()+" "+index);
- }
- }
- }
- public static int[] shiftTable(String pattern){
- int [] table=new int[256];
- int m=pattern.length();
- for(int i=0;i<table.length;i++){
- table[i]=m;
- }
- for(int j=0;j<m-1;j++){
- table[pattern.charAt(j)]=m-1-j;
- }
- return table;
- }
- public static int horsPool(String pattern,String text){
- int[] table=shiftTable(pattern);
- int m=pattern.length();
- int n=text.length();
- int i=m-1;
- while(i<=n-1){
- int k=0;
- while(k<=m-1 && pattern.charAt(m-1-k)==text.charAt(i-k)){
- k=k+1;
- }
- if(k==m){
- return i-m+1;
- }else{
- i=i+table[text.charAt(i)];
- }
- }
- return -1;
- }
- }
- class TestCase{
- int id;
- String pattern;
- String text;
- public int getId() {
- return id;
- }
- public void setId(int id) {
- this.id = id;
- }
- public String getPattern() {
- return pattern;
- }
- public void setPattern(String pattern) {
- this.pattern = pattern;
- }
- public String getText() {
- return text;
- }
- public void setText(String text) {
- this.text = text;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement