Aizu Online Judge 1215 Co-occurrence Search

■1215 Co-occurrence Search

しゃくとり法で解くことが出来る．入力がややこしく，無限ループによるTLEを連発してしまった．

view plainprint?

1. import java.util.*;  
2. import java.lang.*;  
3. import java.math.*;  
4. import java.io.*;  
5.   
6. import static java.lang.Math.*;  
7. import static java.util.Arrays.*;  
8.   
9. public class Main{  
10.   
11.  Scanner sc=new Scanner(System.in);  
12.   
13.  int INF=1<<28;  
14.  double EPS=1e-9;  
15.   
16.  char[] s, key;  
17.   
18.  void run(){  
19.   for(;;){  
20.    StringBuffer lines=new StringBuffer();  
21.    for(;;){  
22.     String line=sc.nextLine();  
23.     if(line.equals("")){  
24.      break;  
25.     }  
26.     lines.append(line);  
27.    }  
28.    s=lines.toString().toCharArray();  
29.    key=sc.nextLine().toCharArray();  
30.    solve();  
31.    if(sc.hasNext()){  
32.     sc.nextLine();  
33.    }else{  
34.     break;  
35.    }  
36.   }  
37.   System.out.flush();  
38.  }  
39.   
40.  void solve(){  
41.   int i=0, j=0;  
42.   int num=0;  
43.   int n=s.length;  
44.   
45.   int min=INF;  
46.   int cMin=0, iMin=0, jMin=0;  
47.   
48.   int nKey=0;  
49.   boolean[] isKey=new boolean[256];  
50.   for(char c : key){  
51.    isKey[c]=true;  
52.   }  
53.   for(boolean b : isKey){  
54.    nKey+=b?1:0;  
55.   }  
56.   int[] count=new int[256];  
57.   
58.   for(;;){  
59.    for(; j<n&&num<nKey; j++){  
60.     if(isKey[s[j]]&&count[s[j]]++==0){  
61.      num++;  
62.     }  
63.    }  
64.   
65.    if(num<nKey){  
66.     break;  
67.    }  
68.   
69.    if(j-i<min){  
70.     iMin=i;  
71.     jMin=j;  
72.     min=j-i;  
73.     cMin=1;  
74.    }else if(j-i==min){  
75.     cMin++;  
76.    }  
77.   
78.    if(isKey[s[i]]&&--count[s[i]]==0){  
79.     num--;  
80.    }  
81.    i++;  
82.   }  
83.   
84.   println(cMin+"\n");  
85.   if(cMin>0){  
86.    String ans=new String(s, iMin, jMin-iMin);  
87.    for(int k=0; k<(ans.length()-1)/72+1; k++){  
88.     println(ans.substring(k*72, min((k+1)*72, ans.length())));  
89.    }  
90.    println("");  
91.   }  
92.  }  
93.   
94.  void debug(Object... os){  
95.   System.err.println(Arrays.deepToString(os));  
96.  }  
97.   
98.  void print(String s){  
99.   System.out.print(s);  
100.  }  
101.   
102.  void println(String s){  
103.   System.out.println(s);  
104.  }  
105.   
106.  public static void main(String[] args){  
107.   // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));  
108.   new Main().run();  
109.  }  
110. }  

import java.util.*;
import java.lang.*;
import java.math.*;
import java.io.*;

import static java.lang.Math.*;
import static java.util.Arrays.*;

public class Main{

 Scanner sc=new Scanner(System.in);

 int INF=1<<28;
 double EPS=1e-9;

 char[] s, key;

 void run(){
  for(;;){
   StringBuffer lines=new StringBuffer();
   for(;;){
    String line=sc.nextLine();
    if(line.equals("")){
     break;
    }
    lines.append(line);
   }
   s=lines.toString().toCharArray();
   key=sc.nextLine().toCharArray();
   solve();
   if(sc.hasNext()){
    sc.nextLine();
   }else{
    break;
   }
  }
  System.out.flush();
 }

 void solve(){
  int i=0, j=0;
  int num=0;
  int n=s.length;

  int min=INF;
  int cMin=0, iMin=0, jMin=0;

  int nKey=0;
  boolean[] isKey=new boolean[256];
  for(char c : key){
   isKey[c]=true;
  }
  for(boolean b : isKey){
   nKey+=b?1:0;
  }
  int[] count=new int[256];

  for(;;){
   for(; j<n&&num<nKey; j++){
    if(isKey[s[j]]&&count[s[j]]++==0){
     num++;
    }
   }

   if(num<nKey){
    break;
   }

   if(j-i<min){
    iMin=i;
    jMin=j;
    min=j-i;
    cMin=1;
   }else if(j-i==min){
    cMin++;
   }

   if(isKey[s[i]]&&--count[s[i]]==0){
    num--;
   }
   i++;
  }

  println(cMin+"\n");
  if(cMin>0){
   String ans=new String(s, iMin, jMin-iMin);
   for(int k=0; k<(ans.length()-1)/72+1; k++){
    println(ans.substring(k*72, min((k+1)*72, ans.length())));
   }
   println("");
  }
 }

 void debug(Object... os){
  System.err.println(Arrays.deepToString(os));
 }

 void print(String s){
  System.out.print(s);
 }

 void println(String s){
  System.out.println(s);
 }

 public static void main(String[] args){
  // System.setOut(new PrintStream(new BufferedOutputStream(System.out)));
  new Main().run();
 }
}