Advertisement
Guest User

jte

a guest
Sep 8th, 2011
141
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 3.50 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_tb extends Thread {
  18.  
  19.     private static final int MODULO = 31;
  20.  
  21.     public B_tb(){
  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.             int ret = 0;
  52.  
  53.             int size = max(begin.length(), end.length());
  54.             for (int len = size; len <= all.length(); ++len) {
  55.                 finalHashes.clear();
  56.                 for (int i = 0; i + len <= all.length(); ++i) {
  57.                     int j = i + len - 1;
  58.                     long currentBegin = hashed[i + begin.length() - 1] - (i == 0 ? 0 : hashed[i - 1]);
  59.                     long currentEnd = hashed[j] - (j - end.length() + 1 == 0 ? 0 : hashed[j - end.length()]);
  60.                     if (currentBegin == beginHash * powers[i] && currentEnd == endHash * powers[j - end.length() + 1]) {
  61.                         finalHashes.add((hashed[j] - (i == 0 ? 0 : hashed[i - 1])) * powers[5500 - j]);
  62.                     }
  63.                 }
  64.                 ret += finalHashes.size();
  65.             }
  66.             output.println(ret);
  67.             output.flush();
  68.             output.close();
  69.         } catch (Throwable e) {
  70.             System.err.println(e.getMessage());
  71.             System.err.println(Arrays.deepToString(e.getStackTrace()));
  72.         }  
  73.    }
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
  81.  
  82.     public static void main(String []args){
  83.         new B_tb().start();
  84.     }
  85.  
  86.     private int nextInt() throws  IOException{
  87.         return Integer.parseInt(nextToken());
  88.     }
  89.  
  90.     private double nextDouble() throws  IOException{
  91.         return Double.parseDouble(nextToken());
  92.     }
  93.  
  94.     private long nextLong() throws  IOException{
  95.         return Long.parseLong(nextToken());
  96.     }
  97.  
  98.     private String nextToken() throws IOException {
  99.         while (tokens == null || !tokens.hasMoreTokens()){
  100.             tokens = new StringTokenizer(input.readLine());
  101.         }
  102.         return tokens.nextToken();
  103.     }
  104.  
  105.     private BufferedReader input;
  106.     private PrintWriter output;
  107.     private StringTokenizer tokens;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement