Advertisement
Guest User

jte

a guest
Sep 8th, 2011
134
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.36 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4. import java.io.PrintWriter;
  5. import java.util.Arrays;
  6. import java.util.HashSet;
  7. import java.util.StringTokenizer;
  8. import static java.lang.Math.*;
  9.  
  10. /**
  11.  * Created by IntelliJ IDEA.
  12.  * User: Taras_Brzezinsky
  13.  * Date: 6/18/11
  14.  * Time: 10:15 PM
  15.  * To change this template use File | Settings | File Templates.
  16.  */
  17. public class B extends Thread {
  18.  
  19.     private static final int MODULO = 31;
  20.  
  21.     public B(){
  22.         this.setPriority(Thread.MAX_PRIORITY);
  23.         this.input = new BufferedReader(new InputStreamReader(System.in));
  24.         this.output = new PrintWriter(System.out);
  25.         this.tokens = null;
  26.     }
  27.  
  28.     public void run(){
  29.         try{
  30.             String all = nextToken();
  31.             String begin = nextToken();
  32.             String end = nextToken();
  33.             long []powers = new long[6000];
  34.             powers[0] = 1;
  35.             for (int i = 1; i < 6000; ++i){
  36.                 powers[i] = powers[i - 1] * MODULO;
  37.             }
  38.             HashSet<Long> finalHashes = new HashSet<Long>();
  39.             long []hashed = new long[all.length()];
  40.             long beginHash = 0, endHash = 0;
  41.             for (int i = 0; i < begin.length(); ++i){
  42.                 beginHash += (begin.charAt(i) - 'a' + 1) * powers[i];
  43.             }
  44.             for (int i = 0; i < end.length(); ++i){
  45.                 endHash += (end.charAt(i) - 'a' + 1) * powers[i];
  46.             }
  47.             hashed[0] = all.charAt(0) - 'a' + 1;
  48.             for (int i = 1; i < all.length(); ++i){
  49.                 hashed[i] = hashed[i - 1] + (all.charAt(i) - 'a' + 1) * powers[i];
  50.             }
  51.  
  52.  
  53.             int size = max(begin.length(), end.length());
  54.             for (int i = 0; i + size <= all.length(); ++i){
  55.                 for (int j = i + size - 1; j < all.length(); ++j){
  56.                     long currentBegin = hashed[i + begin.length() - 1] - (i == 0 ? 0 : hashed[i - 1]);
  57.                     long currentEnd = hashed[j] - (j - end.length() + 1 == 0? 0 : hashed[j - end.length()]);
  58.                     if (currentBegin == beginHash * powers[i] && currentEnd == endHash * powers[j - end.length() + 1]){
  59.                         finalHashes.add((hashed[j] - (i == 0? 0 : hashed[i - 1])) * powers[5500 - j]);
  60.                     }
  61.                 }
  62.             }
  63.             output.println(finalHashes.size());
  64.             output.flush();
  65.             output.close();
  66.         }
  67.         catch(Throwable e){
  68.             System.err.println(e.getMessage());
  69.             System.err.println(Arrays.deepToString(e.getStackTrace()));
  70.         }
  71.     }
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.     public static void main(String []args){
  81.         new B().start();
  82.     }
  83.  
  84.     private int nextInt() throws  IOException{
  85.         return Integer.parseInt(nextToken());
  86.     }
  87.  
  88.     private double nextDouble() throws  IOException{
  89.         return Double.parseDouble(nextToken());
  90.     }
  91.  
  92.     private long nextLong() throws  IOException{
  93.         return Long.parseLong(nextToken());
  94.     }
  95.  
  96.     private String nextToken() throws IOException {
  97.         while (tokens == null || !tokens.hasMoreTokens()){
  98.             tokens = new StringTokenizer(input.readLine());
  99.         }
  100.         return tokens.nextToken();
  101.     }
  102.  
  103.     private BufferedReader input;
  104.     private PrintWriter output;
  105.     private StringTokenizer tokens;
  106. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement